Skip to main content

1642. Furthest Building You Can Reach

medium

Cross a row of buildings using a limited supply of bricks or ladders, maximizing reach. A greedy + min-heap problem where the heap holds the climbs where you spent ladders.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders. You start your journey from building 0 and move to the next building by possibly using bricks or ladders. While moving from building i to building i+1 (0-indexed), if the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks. If the current building's height is less than the next building's height, you can either use one ladder or (h[i+1] - h[i]) bricks. Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Constraints

  • 1 <= heights.length <= 10^5
  • 1 <= heights[i] <= 10^6
  • 0 <= bricks <= 10^9
  • 0 <= ladders <= heights.length

Examples

Example 1

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

Explanation: Walk forward: from 4→2 no cost (going down). 2→7 climb 5. 7→6 no cost. 6→9 climb 3. 9→14 climb 5 — use the ladder. Reaches building 5. Wait — answer is 4 because using bricks first leaves you stuck. Save the ladder for the biggest climb.

Example 2

Input
heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output
7

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Going down or staying level is free. Only climbs cost something.

Hint 2

Greedy: spend ladders on the largest climbs. But you don't know which climbs are largest until you've seen them all — or do you?

Hint 3

Use ladders on every climb up front. When ladders run out, look at the smallest climb you spent a ladder on. Swap: take that ladder back, pay with bricks instead.

Hint 4

A min-heap of the climbs where you used ladders makes 'smallest ladder-spent climb' an O(log n) op.

Solution approach

Reveal approach

Walk index by index and track a min-heap of climb sizes where you've spent a ladder. At each climb d = heights[i+1] - heights[i] (if positive), push d into the heap. If heap size now exceeds ladders, pop the smallest climb the heap holds and subtract it from your brick budget — that climb is now being paid with bricks instead. If bricks go negative, return i (you couldn't even reach i+1). Otherwise continue. At the end, return heights.length - 1. The min-heap lets you always demote your *cheapest* ladder use to bricks — keeping ladders on the most expensive climbs without needing future knowledge. O(n log n) time, O(ladders) space.

Complexity

Time
O(n log n)
Space
O(ladders)

Related patterns

  • heap
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

More Heaps practice problems

See all Heaps problems →