Furthest Building You Can Reach - Leetcode Solution

Problem statement:

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.

Solution:

To solve this problem, we need to start with the assumption that we can always move to the next building without using any bricks or ladders if its height is less than or equal to the current building's height. This means that we need to focus on the cases where the next building's height is greater than the current building's height.

One thing to notice is that we can always use a ladder to move to the next building if we have a ladder available, regardless of the height difference. Therefore, we should use ladders as much as possible and only use bricks when we don't have any ladders left.

Another thing to notice is that we only need to care about the height difference between the current building and the next building, regardless of the other buildings' heights. This means that we can ignore the buildings that are lower than the current building on our way to the furthest building.

With these observations in mind, we can use a priority queue to keep track of the height differences between the current building and the next building. We can iterate over the buildings and for each pair of adjacent buildings, we can add the height difference to the priority queue.

If we have more ladders available than the number of height differences in the priority queue, we can use all the ladders and move to the furthest building without using any bricks. If we don't have enough ladders, we should use bricks to cover the height differences starting from the smallest until we run out of bricks or reach the furthest building.

The code for this approach is as follows:

import java.util.*;

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // min heap of height differences
        int n = heights.length;
        int cur = 0;
        for (int i = 1; i < n; i++) {
            int diff = heights[i] - heights[i - 1];
            if (diff <= 0) {
                // no need for ladder or bricks, continue to next building
                cur = i;
            } else {
                pq.offer(diff);
                if (pq.size() > ladders) {
                    // use bricks to cover the smallest height difference
                    bricks -= pq.poll();
                    if (bricks < 0) {
                        // cannot cover the height difference, return the previous building
                        return cur;
                    }
                }
                cur = i;
            }
        }
        return cur;
    }
}

Time complexity: O(n log n), where n is the number of buildings. The priority queue can have at most n elements, and each operation on the priority queue takes O(log n) time.

1