# 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

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 PriorityQueuemaxHeap = 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