[Solved] Furthest Building You Can Reach C++, Java, Python – Microsoft, Google , Amazon, Media.net-1642

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.

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

Solution

Java || C++|| Easy Solution – Beginners Friendly – Detailed Approach – Simple Solution

Intuition

We have two possible cases with subparts, which are:

1. You can go to next building without any bricks or ladders, if your current building’s size is greater or equal than next building.
2. In case your next building size is greater than your current building, you can use,
   A) Bricks
   We want to optimize our bricks resources such that, we should use bricks for small heights.
   B) Ladders
   For maximum Heights, we should use ladders.

Approach

For storing maximum heights for ladders, we will use Max Heap so that we can poll its peak height in the future.

1. We will create Max Heap.
2. We initialize our result variable as 0, because it will store the total heights until i. In this manner, it stores resources until it indexes.
3. We start from the first building, which is i (i = 0), and we iterate till the array length is -1. Because it will be the last index that we compare.
4. We calculate the difference between next height and the present height.
5. If difference is less than or equal to 0, we can easily go to the next building. And continue to step 4, iterate again.
6. In case if next height is greater than present height, we calculate resources and store in result till index i.
7. We also add difference in max heap so that the maximum difference will be on top of heap.
8. After that we check our resources, we check if our bricks greater than resources result, then we just need to continue over the loop. So thats why I skipped that part.
9. In case if bricks are less than resources result, we will use our hashmap ladder and poll its first element and utilize it.
10. We subtract our HashMap poll resource to resources result so that it means we will use top resource height as an array.
11. After that we will check if ladders are greater than 0, then subtract 1 ladder from it. By utilizing as a HashMap ladder height resources.
12. If ladders are 0 or equal to 0 then we return i. Because we cant move next building. We dont have any resources either bricks or ladders and return current building position.
13. At last return last index of our array.

Complexity

• Time complexity: O(N logk)
• Space complexity: O(N)

class Solution {
public:
    int furthestBuilding(std::vector<int>& heights, int bricks, int ladders) {
        std::priority_queue<int> pq;
        int result = 0;
        for (int i = 0; i < heights.size() - 1; ++i) {
            int diff = heights[i + 1] - heights[i];
            if (diff <= 0) {
                continue;
            }
            result += diff;
            pq.push(diff);
            if (bricks < result) {
                result -= pq.top();
                pq.pop();
                if (ladders > 0) {
                    ladders--;
                } else {
                    return i;
                }
            }
        }
        return heights.size() - 1;
    }
};

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        int result =0;
        for(int i=0;i<heights.length-1;i++){
            int diff = heights[i+1] - heights[i];// 7-2 =5
            if(diff<=0){
                continue;
            }
             result = result + diff;
             pq.add(diff);
             if(bricks<result){
                 result = result - pq.poll();
                 if(ladders>0){ladders--;}
                 else return i;    
             }  
        }
        return heights.length-1;   
    }
}

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        n = len(heights)
        return self.solve(heights, 0, bricks, ladders)

    def solve(self, heights: List[int], i: int, bricks: int, ladders: int) -> int:
        if i == len(heights) - 1:
            return i
        diff = heights[i + 1] - heights[i]
        if diff > 0:
            ans = i
            if bricks >= diff:
                ans = max(ans, self.solve(heights, i + 1, bricks - diff, ladders))
            if ladders > 0:
                ans = max(ans, self.solve(heights, i + 1, bricks, ladders - 1))
            return ans
        else:
            return self.solve(heights, i + 1, bricks, ladders)