0401MediumArrayGreedyHeap (Priority Queue)

Furthest Relay Mast

Tracked in this browser only

Trains the technique from

LeetCode 1642Furthest Building You Can Reach

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Relay masts stand in a row along a ridge, and masts[i] is the height of mast i in metres. A technician begins at mast 0 and only ever moves to the mast immediately to the right.

Moving from mast i to mast i + 1 is free whenever masts[i + 1] <= masts[i]. When masts[i + 1] > masts[i], that one move has to be paid for in exactly one of two ways:

spend masts[i + 1] - masts[i] metres out of the cable metres on the reel, or
spend one of the hoists, which covers a rise of any size.

Both supplies are shared across the whole walk, and neither is refunded. Spend them however you like, and return the index of the furthest mast the technician can end up standing on.

Examples

Example 1

Input: masts = [3,6,4,10], cable = 2, hoists = 1
Output: 2

Spending the hoist on the 3 metre rise from mast 0 to mast 1 gets the technician there, and mast 1 to mast 2 drops in height so it is free. The rise from mast 2 to mast 3 is 6 metres, with no hoist left and only 2 metres of cable, so mast 2 is the end of the walk.

Example 2

Input: masts = [8,5,5,9,11], cable = 4, hoists = 0
Output: 3

The first move drops, the second is level, and both are free. Paying the 4 metre rise into mast 3 empties the reel, and the 2 metre rise into mast 4 then cannot be paid at all.

Example 3

Input: masts = [2,9], cable = 0, hoists = 1
Output: 1

The single 7 metre rise is covered by the one hoist, which works for a rise of any size.

Example 4

Input: masts = [7,7,7], cable = 0, hoists = 0
Output: 2

Neither move goes up, so both are free and the empty supplies never matter.

Example 5

Input: masts = [1,4,2,20,21], cable = 3, hoists = 1
Output: 3

Paying the 3 metre rise into mast 1 with cable and the 18 metre rise into mast 3 with the hoist reaches mast 3. The 1 metre rise into mast 4 is then unpayable, since the reel is empty and the hoist is gone.

Constraints

1 <= masts.length <= 10^5
1 <= masts[i] <= 10^6
0 <= cable <= 10^9
0 <= hoists <= masts.length

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def furthest_building(masts: list[int], cable: int, hoists: int) -> int:

Java

public int furthestBuilding(int[] masts, int cable, int hoists)

The intended approach

Time O(n log(hoists + 1))Space O(min(n, hoists) + 1) for the heap

Walk left to right and provisionally assign a hoist to every rise, keeping those rises in a min-heap. As soon as the heap holds more rises than there are hoists, pull out its smallest entry and pay for that one with cable instead, which keeps the hoists on the largest rises seen so far. The moment the cable reel goes negative, the current mast index is as far as the walk reaches.

Pythonentry point: furthest_building

import heapq


def furthest_building(masts, cable, hoists):
    # Time O(n log(hoists + 1)): one pass, and each rise enters and leaves a
    # heap that never holds more than hoists + 1 entries.
    # Space O(min(n, hoists) + 1) for that heap.
    hoisted = []
    left = cable
    for i in range(len(masts) - 1):
        rise = masts[i + 1] - masts[i]
        if rise <= 0:
            continue
        heapq.heappush(hoisted, rise)
        if len(hoisted) > hoists:
            left -= heapq.heappop(hoisted)
            if left < 0:
                return i
    return len(masts) - 1

The obvious version

For each candidate end mast, collect every rise up to it, sort those rises from largest down, cover the first hoists of them with hoists, and check whether the cable reel covers the rest.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_furthest_building(masts, cable, hoists):
    best = 0
    for end in range(1, len(masts)):
        rises = []
        for i in range(end):
            rise = masts[i + 1] - masts[i]
            if rise > 0:
                rises.append(rise)
        rises.sort(reverse=True)
        needed = 0
        for value in rises[hoists:]:
            needed += value
        if needed <= cable:
            best = end
        else:
            break
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in