Furthest Building You Can Reach - LeetCode Daily Challenge

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.

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

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        
        PriorityQueue<Integer> diff = new PriorityQueue<>((n1, n2) -> (n2 - n1));
        int i;
        for(i = 0; i < heights.length - 1; i++) {
            if(heights[i] >= heights[i + 1]) continue;
            int d = heights[i + 1] - heights[i];

            if(bricks >= d) {
                bricks -= d;
                diff.add(d);
            } else if(ladders > 0){
                if(diff.size()>0) {
                    int x = diff.peek();
                    if(x > d) {
                        bricks += x;
                        diff.poll();
                        diff.add(d);
                        bricks -= d;
                    } 
                }
                ladders -= 1;
            } else {
                break;
            }
        }

        return i; 
    }
}

C++ Code

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int> diff;
        int i;
        for(i = 0; i < heights.size() - 1; i++) {
            if(heights[i] >= heights[i + 1]) continue;
            int d = heights[i + 1] - heights[i];

            if(bricks >= d) {
                bricks -= d;
                diff.push(d);
            } else if(ladders > 0){
                if(!diff.empty()) {
                    int x = diff.top();
                    if(x > d) {
                        bricks += x;
                        diff.pop();
                        diff.push(d);
                        bricks -= d;
                    } 
                }
                ladders -= 1;
            } else {
                break;
            }
        }
        return i;        
    }
};

Python Code

class Solution(object):
    def furthestBuilding(self, heights, bricks, ladders):
        diff = []
        i = 0
        while i < len(heights) - 1:
            if heights[i] >= heights[i + 1]:
                i += 1
                continue
            d = heights[i + 1] - heights[i]

            if bricks >= d:
                bricks -= d
                heapq.heappush(diff, -d)
            elif ladders > 0:
                if diff:
                    x = -diff[0]
                    if x > d:
                        bricks += x
                        heapq.heappop(diff)
                        heapq.heappush(diff, -d)
                        bricks -= d
                ladders -= 1
            else:
                break
            i += 1

        return i

Javascript Code

// remove this comment and paste the code

Go Code

// remove this comment and paste the code

Complexity Analysis

Time Complexity: O(N * logN)
Space Complexity: O(N)