1642. Furthest Building You Can Reach - Detailed Explanation

Problem Statement

Description:
You are given an array of integers heights representing the heights of buildings, along with an integer bricks and an integer ladders. You start at building 0 and move to building 1, 2, and so on. To move from building i to building i+1:

• If heights[i+1] is less than or equal to heights[i], you can move without using any resources.

• If heights[i+1] is greater than heights[i], you must either use bricks equal to the difference (heights[i+1] - heights[i]) or use one ladder.

Your goal is to reach as far as possible along the array of buildings. Return the index of the furthest building you can reach by using the given bricks and ladders optimally.

Examples:

1. Example 1:

   • Input:
     heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1
   • Output: 4
   • Explanation:
     • From building 0 (4) to 1 (2): No resource is needed because the next building is lower.
     • From building 1 (2) to 2 (7): The climb is 5. Use 5 bricks.
     • From building 2 (7) to 3 (6): No resource is needed.
     • From building 3 (6) to 4 (9): The climb is 3. Use 1 ladder.
     • From building 4 (9) to 5 (14): The climb is 5, but no bricks or ladders remain. Thus, you stop at building 4.

2. Example 2:

   • Input:
     heights = [4, 12, 2, 7, 3, 18, 20, 3, 19], bricks = 10, ladders = 2
   • Output: 7
   • Explanation:
     The optimal assignment of bricks and ladders allows you to reach building 7 but not building 8.

3. Example 3:

   • Input:
     heights = [14, 3, 19, 3], bricks = 17, ladders = 0
   • Output: 3
   • Explanation:
     With no ladders available, you must use bricks for all climbs. The available bricks let you reach the last building.

Constraints:

• (1 \leq \text{heights.length} \leq 10^5)
• (1 \leq \text{heights}[i] \leq 10^6)
• (0 \leq \text{bricks} \leq 10^9)
• (0 \leq \text{ladders} \leq \text{heights.length})

Hints Before the Solution

1. Optimal Resource Allocation:
   Instead of deciding upfront which climbs should use bricks or ladders, try to postpone the decision. Use bricks by default for each climb, but when you run out of bricks, consider replacing one of the previous brick uses with a ladder if that climb was expensive.

2. Greedy with Min-Heap:
   A min-heap can help you keep track of all the positive climbs (differences) you have encountered. By always converting the smallest brick expense into a ladder use when necessary, you save bricks for larger climbs.

Approaches

Approach 1: Greedy with Min-Heap (Optimal)

Idea:

• Iterate Through Buildings:
  As you move from building i to building i+1, calculate the positive difference diff = heights[i+1] - heights[i] (only if the next building is taller).

• Use a Min-Heap:
  Push each positive difference onto a min-heap. This heap tracks all climbs where you have “spent” bricks.

• Reallocate Bricks with Ladders:
  If the size of the heap exceeds the number of available ladders, pop the smallest climb from the heap and subtract that value from bricks. This effectively means you are retroactively using a ladder for the smallest climb (saving bricks for larger climbs).

• Stop When Bricks Run Out:
  If at any point bricks becomes negative, you can’t pay for the required climb, so return the current building index.

Why It Works:

• The min-heap helps ensure that ladders are used for the largest climbs (by converting the smallest brick expense into a ladder when possible). This minimizes the total bricks spent, allowing you to reach as far as possible.

Code Implementations

Python Implementation