Medium

Furthest Building You Can Reach

LAB

Given building heights, bricks, and ladders, return the furthest index reachable while paying positive climbs with bricks or ladders.

EXAMPLES

Example 1

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

Output
4

FUNCTION SHAPE

heights: intArraybricks: intladders: int→int

SOLUTION NOTE

The first solution is greedy heap. The second is with binary search.

The problem with just using a pure greedy approach, similar to binary search is that we could be using a ladder for a huge gap, but huge gap is at the end, where we would have never reached there anyways. (ie. there is no fixed length) This is why we either need to use a greedy heap solution where we swap ladders with bricks on the fly as we move left to right. OR we can fix the final building length using binary search, and once we fix the length we can use a simple greedy solution.

Binary search solution should be fairly straightforward. Max template.

Open on LeetCode ↗