Furthest Building You Can Reach

Furthest Building You Can Reach

What is this problem about?

The Furthest Building You Can Reach interview question asks you to navigate a series of buildings of varying heights. You start at building 0. To move to the next building, if it is taller, you must use either bricks or ladders to cover the height difference. You have a limited number of bricks and ladders. A ladder covers any height difference, while a brick covers exactly one unit of height. You want to find the index of the furthest building you can reach.

Why is this asked in interviews?

This is a very popular Greedy and Heap interview pattern problem asked by companies like Uber, Amazon, and Google. It tests your ability to optimize resource usage. The core challenge is deciding when to use a ladder versus bricks. You can't just greedily use bricks until they run out, because you might waste them on a massive jump that a ladder could have covered.

Algorithmic pattern used

The problem is solved using a Greedy approach with a Min-Heap.

1. Always use ladders first for every positive height difference.
2. Store the height differences covered by ladders in a Min-Heap.
3. When you run out of ladders, look at the Min-Heap. The top of the heap is the smallest jump you used a ladder for.
4. It is optimal to replace that ladder with bricks. Pop the smallest jump from the heap, subtract it from your bricks count, and use the freed-up ladder for the current, larger jump.
5. If bricks drops below 0, you cannot make the current jump. Return the current building index.

Example explanation

Heights: [4, 2, 7, 6, 9, 14, 12], Bricks: 5, Ladders: 1

1. 4 -> 2: Downhill. Go to 1.
2. 2 -> 7: Diff 5. Use ladder. Heap: [5]. Go to 2.
3. 7 -> 6: Downhill. Go to 3.
4. 6 -> 9: Diff 3. No ladders left. Min jump in heap is 5.
   • Current jump is 3. Since $3 < 5$, use bricks for the current jump.
   • bricks = 5 - 3 = 2. Heap remains [5]. Go to 4.
5. 9 -> 14: Diff 5. No ladders. Min jump in heap is 5.
   • Replace ladder on jump 5 with bricks? Need 5 bricks, only have 2. Impossible! Stop at building 4.

Common mistakes candidates make

• Max-Heap of Bricks: Trying to use bricks first and a max-heap to replace the largest brick usage with a ladder. While logically similar, it's slightly harder to implement cleanly than the Min-Heap of ladders approach.
• Greedy Failure: Using bricks for everything until they run out, then using ladders. This fails because a ladder is best used on the absolute largest jumps.
• Integer Overflow: Forgetting that height differences and brick sums can exceed 32-bit limits.

Interview preparation tip

This is the quintessential "retroactive greedy" problem. You make a choice (use a ladder), but keep a record of it so you can "undo" that choice later if a better opportunity arises. This is a very powerful pattern.