Solution For Furthest Building You Can Reach

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 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.

Step by Step Implementation For Furthest Building You Can Reach

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        // maxHeap will store the difference between adjacent buildings
        PriorityQueue maxHeap = new PriorityQueue<>();
        
        // we need to keep track of the furthest building we can reach
        // with the given number of bricks and ladders
        int furthestReach = 0;
        
        for (int i = 1; i < heights.length; i++) {
            int diff = heights[i] - heights[i-1];
            // if the difference is positive, it means we need bricks to build
            // the higher building
            if (diff > 0) {
                // we add the difference to the max heap
                maxHeap.add(diff);
                // we need to keep track of the number of bricks we have used
                bricks -= diff;
                // if the number of bricks becomes negative, it means we can't
                // reach the current building
                if (bricks < 0) {
                    // we check if we have any ladders left
                    if (ladders == 0) {
                        // if we don't have any ladders left, we return the
                        // furthest building we could reach
                        return furthestReach;
                    }
                    // if we have ladders left, we use one ladder to reach the
                    // current building
                    ladders--;
                    // we also need to add the difference back to the number of
                    // bricks because we used one ladder
                    bricks += diff;
                }
            }
            // we update the furthest building we can reach
            furthestReach = i;
        }
        // if we reach this point, it means we can reach all the buildings
        return furthestReach;
    }
}

This problem can be solved using a greedy algorithm. We can keep track of the tallest building we can reach at each index and update it as we iterate through the array. Then, we can just return the last element in our array, which will be the furthest building we can reach.

def furthestBuilding(heights, bricks, ladders):

# keep track of the tallest building we can reach at each index
max_reached = [0] * len(heights)

# update our max height for each index
for i in range(len(heights)):

# check if we can use a ladder to reach the current building
if ladders > 0 and heights[i] > max_reached[i]:

# use a ladder and update our max height
max_reached[i] = heights[i]
ladders -= 1

# check if we can reach the current building with our bricks
elif bricks >= heights[i] - max_reached[i]:

# update our max height
max_reached[i] = heights[i]

# we used some bricks, so update our count
bricks -= heights[i] - max_reached[i]

# we couldn't reach the current building, so stop
else:

# we return i - 1 because we haven't reached the end of the array yet
return i - 1

# we made it to the end of the array, so return the last index
return len(heights) - 1

/**
 * @param {number[]} heights
 * @return {number}
 */
 var furthestBuilding = function(heights) {
    
    // create a max heap to store the differences in height
    // as we iterate through the array
    let heap = new MaxHeap();
    
    // store the largest difference in height so far
    let maxDiff = 0;
    
    // iterate through the array
    for (let i = 0; i < heights.length - 1; i++) {
        // calculate the difference in height between adjacent buildings
        let diff = Math.abs(heights[i+1] - heights[i]);
        // update the maxDiff if necessary
        if (diff > maxDiff) {
            maxDiff = diff;
        }
        // add the difference to the heap
        heap.insert(diff);
        // if the difference is greater than the maxDiff, we can't reach
        // the furthest building
        if (diff > maxDiff) {
            return i;
        }
    }
    // if we reach this point, we can reach the furthest building
    return heights.length - 1;
};

class Solution {
public:
    int furthestBuilding(vector& heights, int bricks, int ladders) {
        // We will use a priority queue to track the buildings that we can reach
        // The priority queue will be sorted by the height of the building
        priority_queue, greater> pq;
        
        // We will keep track of the current height and the furthest building we can reach
        int curr_height = 0, furthest = 0;
        
        // We will iterate through the buildings
        for (int i = 0; i < heights.size(); i++) {
            // If the current building is taller than the one before it, we need bricks to reach it
            if (heights[i] > curr_height) {
                // We will keep track of the difference in height
                int diff = heights[i] - curr_height;
                
                // We will try to use ladders first
                while (ladders > 0 && !pq.empty() && pq.top() <= heights[i]) {
                    // If the height of the building in the queue is less than or equal to the current building, we can use a ladder
                    diff -= pq.top() - curr_height;
                    pq.pop();
                    ladders--;
                }
                
                // If we still need bricks, we will try to use bricks
                if (diff > 0) {
                    // We will try to use as many bricks as possible
                    while (bricks >= diff) {
                        bricks -= diff;
                        diff = 0;
                    }
                    
                    // If we used up all our bricks and we still need more, we can't reach the current building
                    if (diff > 0) {
                        return furthest;
                    }
                }
            }
            
            // We can always reach the current building, so we will update the furthest building we can reach
            furthest = i;
            
            // We will update the current height
            curr_height = heights[i];
            
            // We will add the current building to the queue
            pq.push(heights[i]);
        }
        
        // We have reached the end, so the furthest building we can reach is the last one
        return furthest;
    }
};

using System; 
  
class GFG { 
      
// Returns the max height tower 
// that can be built from the 
// given array 
static int maxTower(int []arr, int n) 
{ 
      
    // Sort the given array in 
    // descending order 
    Array.Sort(arr); 
    Array.Reverse(arr); 
      
    // Initialize result 
    int res = 0; 
      
    // Iterate through all 
    // elements of the array 
    for (int i = 0; i < n; i ++) 
    { 
        // If the current element is 
        // smaller than next element, 
        // then update the res 
        if (i < n - 1 && arr[i] > arr[i + 1]) 
        { 
            res = Math.Max(res, maxTowerUtil(arr, i + 1, 1)); 
        } 
    } 
      
    return res; 
} 
  
// A recursive utility function 
// to find the maximum tower 
// that can be built from the 
// given array 
static int maxTowerUtil(int []arr, int n, int curr_h) 
{ 
    // Base case 
    if (n == arr.Length) 
        return curr_h; 
  
    // If the current element is 
    // smaller than next element, 
    // then include the current 
    // element and recur for the 
    // remaining array 
    if (n < arr.Length - 1 && arr[n] > arr[n + 1]) 
        return Math.Max(maxTowerUtil(arr, n + 1, curr_h + 1), 
                        maxTowerUtil(arr, n + 1, curr_h)); 
  
    // If the current element is 
    // greater than next element, 
    // then recur for the remaining 
    // array 
    else
        return maxTowerUtil(arr, n + 1, curr_h); 
} 
  
// Driver Code 
public static void Main () 
{ 
    int []arr = {4, 2, 5, 9, 7, 6, 10, 3, 1}; 
    int n = arr.Length; 
    Console.WriteLine(maxTower(arr, n)); 
} 
} 
  
// This code is contributed by Smitha Dinesh Semwal