Formatted question description: https://leetcode.ca/all/1642.html

1642. Furthest Building You Can Reach (Medium)

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.

 

Example 1:

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

Example 2:

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

Example 3:

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

 

Constraints:

  • 1 <= heights.length <= 105
  • 1 <= heights[i] <= 106
  • 0 <= bricks <= 109
  • 0 <= ladders <= heights.length

Related Topics:
Binary Search, Heap

Solution 1. Min heap

Here we only consider positive diffs, and ignore non-positive ones.

We use brick for small diff, and ladder for large diff.

Scan from left to right, maintain a data structure that can efficiently:

  1. sort the diffs
  2. sum the smallest count - L diffs, where count is the count of (positive) diffs we’ve scanned.

Imagine that we already have the diffs sorted.

[small -----------------------------> large ]
// we can split them in this way.
[ sum of count - L items ][ largest L items ]

So we can use a min heap to keep track of the largest L items.

We keep pushing diff into the heap. When it has more than L items, we push the top element to keep heap of size L and add the popped element to sum. The sum is the count of bricks that we need.

When sum is greater than B, we should stop there.

// OJ: https://leetcode.com/problems/furthest-building-you-can-reach/

// Time: O(NlogL)
// Space: O(L)
class Solution {
public:
    int furthestBuilding(vector<int>& H, int B, int L) {
        int N = H.size(), sum = 0;
        priority_queue<int, vector<int>, greater<>> pq; // min-heap, keep track of the L largest diffs
        for (int i = 1; i < N; ++i) {
            int diff = H[i] - H[i - 1];
            if (diff <= 0) continue;
            pq.push(diff);
            if (pq.size() <= L) continue;
            sum += pq.top();
            pq.pop();
            if (sum > B) return i - 1;
        }
        return N - 1;
    }
};

Java

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        int maxIndex = 0;
        int length = heights.length;
        for (int i = 1; i < length && bricks >= 0; i++) {
            if (heights[i] <= heights[i - 1])
                maxIndex = i;
            else {
                int difference = heights[i] - heights[i - 1];
                bricks -= difference;
                priorityQueue.offer(difference);
                while (bricks < 0 && ladders > 0 && !priorityQueue.isEmpty()) {
                    bricks += priorityQueue.poll();
                    ladders--;
                }
                if (bricks >= 0)
                    maxIndex = i;
            }
        }
        return maxIndex;
    }
}

All Problems

All Solutions