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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Furthest Building You Can Reach and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →