Skyscraper Furthest Distance

[#heap]

## description

## Skyscraper Furthest Distance

A player needs to traverse between skyscrapers, carrying springs and sandbags. The heights of these buildings vary.

If the next building's rooftop is lower than or equal to the current one, the player can move freely.

If the next rooftop is higher, the player must either:

–
Use sandbags (each sandbag increases the player's height by 1; if the sum of the current height and sandbags equals the next rooftop's height, the player can move forward).
–
Use springs to jump directly to the next rooftop, regardless of height difference.

The goal is to determine the index of how far the player can travel.

Example 1:

plain text

Input: heights = [2, 3, 5, 1, 7], springs = 1, sandbags = 2
Output: 3
Explanation: Use 1 sandbag to move from 2 -> 3, use 1 spring to move from 3 -> 5, 5 -> 1 is a free move. Cannot move further, therefore, index 3.

Example 2:

plain text

Input: heights = [4, 2, 2, 6, 3, 7], springs = 1, sandbags = 4
Output: 5
Explanation: 4 -> 2 free, 2 -> 2 free, 2 -> 6 use 4 sandbags, 6 -> 3 free, 3 -> 7, need 4 sandbags, use spring. Can also use spring at 2 -> 6 instead, same result

Example 3:

plain text

Input: heights = [1, 5, 2, 3, 10], springs = 1, sandbags = 3
Output: 3
Explanation: 1 -> 5 must use spring, 5 -> 2 free, 2 -> 3 use 1 sandbag, 3 -> 10 need 7 sandbags or 1 spring, don't have either, return 3

## notes

### Intuition

Springs are most valuable for the largest height differences. Use sandbags first, and when you run out, retroactively convert the largest sandbag usage to a spring.

### Implementation

Use a max heap to track height differences. For each upward jump, subtract from sandbags and add the difference to the heap. If sandbags go negative and no springs remain, return the current index. Otherwise, use a spring by popping the largest jump from the heap and adding those sandbags back. Continue until the end.

### Edge-cases

Python's heapq is a min heap—negate values to simulate max heap behavior. Remember to negate again when popping.

–
Time: O(n log n) — heap operations for each building
–
Space: O(n) — heap stores jump sizes

### Complexity

## solution

python

from typing import List
import heapq

class Solution:
    def furthestDistance(self, heights: List[int], springs: int, sandbags: int) -> int:
        # Optimal (min heap, O(n log n) time, O(n) space)
        max_heap = []
        # O(n)
        for i in range(len(heights) - 1):
            diff = heights[i + 1] - heights[i]
            if diff <= 0:
                continue

            sandbags -= diff
            # O(log n)
            heapq.heappush(max_heap, -diff)

            if sandbags < 0:
                if springs == 0:
                    return i
                springs -= 1
                # O(log n)
                sandbags += -heapq.heappop(max_heap)
        return len(heights) - 1

if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()

--EOF--