Problem Description

You are given an array heights where each element represents the height of a building. You start at building 0 and want to travel as far as possible to the right, moving from one building to the next. You have a certain number of bricks and ladders to help you.

When moving from building i to building i+1:

• If the current building's height is greater than or equal to the next building's height, you can move freely without using any resources
• If the current building's height is less than the next building's height (you need to climb up), you have two options:
  • Use one ladder (regardless of the height difference)
  • Use exactly heights[i+1] - heights[i] bricks

Your goal is to find the furthest building index you can reach by using your bricks and ladders optimally.

For example, if heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, and ladders = 1:

• From building 0 (height 4) to building 1 (height 2): Free move (going down)
• From building 1 (height 2) to building 2 (height 7): Need to climb 5 units - could use 5 bricks or 1 ladder
• From building 2 (height 7) to building 3 (height 6): Free move (going down)
• And so on...

The key insight is that you want to use ladders for the largest height differences and bricks for smaller ones to maximize how far you can travel. The solution uses a min-heap to track the smallest climbs where ladders were used, allowing you to swap a ladder for bricks when encountering a larger climb later.

Intuition

The key observation is that ladders are more valuable than bricks because a ladder can overcome any height difference while bricks are consumed based on the actual height difference. This means we should use ladders for the largest gaps and bricks for smaller ones.

But here's the challenge: we don't know all the height differences ahead of time as we traverse the buildings. If we encounter a small gap early on and use a ladder, we might regret it later when we face a much larger gap that could have been a better use of that ladder.

The breakthrough insight is to use a greedy approach with regret:

• Initially, use ladders for the first few climbs we encounter (up to the number of ladders we have)
• Keep track of these climbs in a min-heap
• When we run out of ladders and face a new climb, we can make a smart decision: compare this new climb with the smallest climb where we previously used a ladder
• If we previously used a ladder on a smaller climb, we can "take back" that decision - replace that ladder usage with bricks and use the ladder for the current climb instead

This way, we're always ensuring that our ladders are being used for the largest climbs we've seen so far. The min-heap allows us to efficiently track and retrieve the smallest climb where we've used a ladder.

The algorithm naturally terminates when we either:

1. Run out of bricks (can't afford the next climb even with optimal ladder placement)
2. Successfully reach the last building

This greedy strategy with the ability to revise past decisions guarantees we'll reach the furthest possible building.

Learn more about Greedy and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a min-heap data structure combined with a greedy algorithm to solve this problem optimally.

Here's how the algorithm works step by step:

1. Initialize an empty min-heap h to store the height differences where we've used ladders.

2. Iterate through consecutive buildings from index 0 to len(heights) - 2:

   • Calculate the height difference d = heights[i+1] - heights[i]
   • If d <= 0, we can move freely (going down or same level), so continue to the next building

3. For each upward climb (when d > 0):

   • Push the height difference into the min-heap: heappush(h, d)
   • This represents using a ladder for this climb initially

4. Check if we've used more ladders than available:

   • If len(h) > ladders, we need to replace one ladder usage with bricks
   • Pop the smallest height difference from the heap: smallest = heappop(h)
   • This is the most economical climb to use bricks on instead of a ladder
   • Deduct bricks: bricks -= smallest

5. Check if we have enough bricks:

   • If bricks < 0, we can't make this climb, so return the current index i
   • Otherwise, continue to the next building

6. If we complete the loop, we've successfully reached the last building, so return len(heights) - 1

Why this works:

• The heap always maintains the ladders largest climbs we've encountered so far
• Any climb not in the heap is covered by bricks
• By always keeping the largest climbs for ladders and using bricks for smaller ones, we minimize brick usage
• This greedy approach with dynamic reallocation ensures optimal resource usage

Time Complexity: O(n log k) where n is the number of buildings and k is the number of ladders (due to heap operations)

Space Complexity: O(k) for storing at most k elements in the heap

Example Walkthrough

Let's walk through a concrete example to see how the algorithm works:

Input: heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1

Step-by-step execution:

Initial state: Min-heap h = [], at building 0 (height 4)

Move 0→1:

• Height difference: 2 - 4 = -2 (going down)
• No resources needed, move freely
• Current position: building 1

Move 1→2:

• Height difference: 7 - 2 = 5 (climbing up)
• Push 5 into heap: h = [5]
• Heap size (1) ≤ ladders (1), so we're using our 1 ladder here
• Current position: building 2

Move 2→3:

• Height difference: 6 - 7 = -1 (going down)
• No resources needed, move freely
• Current position: building 3

Move 3→4:

• Height difference: 9 - 6 = 3 (climbing up)
• Push 3 into heap: h = [3, 5] (min-heap, so 3 is at root)
• Heap size (2) > ladders (1), need to use bricks for something
• Pop smallest climb from heap: heappop() = 3
• Now h = [5] (ladder used for the climb of 5)
• Use bricks for the climb of 3: bricks = 5 - 3 = 2
• Bricks ≥ 0, so continue
• Current position: building 4

Move 4→5:

• Height difference: 14 - 9 = 5 (climbing up)
• Push 5 into heap: h = [5, 5]
• Heap size (2) > ladders (1), need to use bricks for something
• Pop smallest climb from heap: heappop() = 5
• Now h = [5] (ladder used for one climb of 5)
• Use bricks for the other climb of 5: bricks = 2 - 5 = -3
• Bricks < 0, cannot make this climb!
• Return current position: 4

Result: The furthest building we can reach is at index 4 (height 9).

Key insights from this example:

1. The algorithm initially assigns ladders to climbs as we encounter them
2. When we exceed our ladder count, we reassign the ladder from the smallest climb to the current climb if beneficial
3. The min-heap ensures we always use ladders for the largest climbs encountered so far
4. We stop when we can't afford the next climb with our remaining bricks

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log k) where n is the length of the heights array and k is the number of ladders.

• The code iterates through the heights array once, which takes O(n) time.
• For each height difference that is positive (requiring either bricks or a ladder), we perform a heap push operation: heappush(h, d), which takes O(log k) time since the heap size is at most k + 1 (number of ladders plus one).
• When the heap size exceeds the number of ladders, we perform a heap pop operation: heappop(h), which also takes O(log k) time.
• In the worst case, we perform heap operations for each building transition, resulting in O(n log k) total time complexity.

Space Complexity: O(k) where k is the number of ladders.

• The heap h stores at most ladders + 1 elements at any given time.
• When the heap size exceeds ladders, we immediately pop the smallest element, maintaining the size constraint.
• Therefore, the space complexity is O(k) for storing the heap.
• The remaining variables (i, a, b, d) use constant space O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling Downward or Level Moves

Pitfall: A common mistake is to process all height differences, including negative ones (going down) or zero differences (same level), which unnecessarily complicates the logic and can lead to incorrect resource allocation.

# INCORRECT - Processing all differences
for i in range(len(heights) - 1):
    height_diff = heights[i + 1] - heights[i]
    heapq.heappush(min_heap, height_diff)  # Wrong! Includes negative values
    if len(min_heap) > ladders:
        bricks -= heapq.heappop(min_heap)
        if bricks < 0:
            return i

Solution: Always check if height_diff > 0 before processing. Only upward climbs require resources:

# CORRECT - Only process upward climbs
if height_diff > 0:
    heapq.heappush(min_heap, height_diff)
    # ... rest of the logic

2. Forgetting to Import heapq or Using Wrong Import Statement

Pitfall: The code uses heapq functions but might forget to import the module, or import it incorrectly when used within a method.

# INCORRECT - Missing import or wrong scope
class Solution:
    def furthestBuilding(self, heights, bricks, ladders):
        min_heap = []
        heappush(min_heap, 5)  # NameError: name 'heappush' is not defined

Solution: Import heapq at the beginning of the method or use the full module name:

# CORRECT - Option 1: Import inside method
def furthestBuilding(self, heights, bricks, ladders):
    import heapq
    min_heap = []
    heapq.heappush(min_heap, 5)

# CORRECT - Option 2: Import at class level
import heapq
class Solution:
    def furthestBuilding(self, heights, bricks, ladders):
        heapq.heappush(min_heap, 5)

3. Off-by-One Error in Loop Range

Pitfall: Using range(len(heights)) instead of range(len(heights) - 1), which causes an index out of bounds error when accessing heights[i + 1].

# INCORRECT - Will cause IndexError
for i in range(len(heights)):  # Goes from 0 to len(heights)-1
    height_diff = heights[i + 1] - heights[i]  # Error when i = len(heights)-1

Solution: Always use range(len(heights) - 1) when comparing consecutive elements:

# CORRECT
for i in range(len(heights) - 1):
    height_diff = heights[i + 1] - heights[i]

4. Using Max Heap Instead of Min Heap

Pitfall: Misunderstanding the algorithm and trying to use a max heap to keep track of the largest jumps, which complicates the logic unnecessarily.

# INCORRECT - Overcomplicating with max heap
min_heap = []
heapq.heappush(min_heap, -height_diff)  # Negating for max heap
if len(min_heap) > ladders:
    bricks -= -heapq.heappop(min_heap)  # Need to negate back

Solution: Use a min heap directly. The algorithm naturally keeps the largest jumps in the heap when the heap size equals the number of ladders:

# CORRECT - Simple min heap
heapq.heappush(min_heap, height_diff)
if len(min_heap) > ladders:
    bricks -= heapq.heappop(min_heap)  # Pops the smallest

5. Returning Wrong Index When Resources Are Exhausted

Pitfall: Returning i + 1 or i - 1 instead of i when we can't make a jump, leading to incorrect results.

# INCORRECT
if bricks < 0:
    return i - 1  # Wrong! We're already at building i
    # or
    return i + 1  # Wrong! We can't reach i+1

Solution: Return i directly - this is the last building we could successfully reach:

# CORRECT
if bricks < 0:
    return i  # This is the furthest we can go