Furthest Building You Can Reach solution and explanation
Google
9 more videos on this problem
Furthest Building You Can Reach - Leetcode 1642 - PythonNeetCodeIO · 11:08 · 22K views
Leectode 1642. Furthest Building You Can ReachFraz · 10:19 · 10K views
Furthest Building You Can Reach | What is Lazy Greedy | Recursion | Memoization | Leetcode 1642codestorywithMIK · 51:23 · 10K views
Furthest Building You Can Reach | Live Coding with Explanation | Leetcode - 1642Algorithms Made Easy · 12:00 · 9K views
1642. Furthest Building You Can Reach | 5 ways | Why not DP | Min Heap | Binary Search | GreedyAryan Mittal · 27:20 · 6K views
Leetcode 1642. Furthest Building You Can ReachCode with Alisha · 24:23 · 3K views
Leetcode 1642 Furthest Building You Can Reach | MinHeap | Checkout Coding Decoded SDE SheetCoding Decoded · 10:46 · 2K views
Leetcode - Furthest Building You Can Reach (Python)Timothy H Chang · 8:52 · 1K views
Daily Leetcode #812: Jun 21, 2022 - 1642. Furthest Building You Can ReachProgramming Live with Larry · 21:58 · 511 views
Furthest Building You Can Reach - Leetcode 1642 - PythonTechError · 7:35 · 360 views
The problem
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
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0 Output: 3
Constraints:
1 <= heights.length <= 1051 <= heights[i] <= 1060 <= bricks <= 1090 <= ladders <= heights.length
Approach overview
Problem Overview: You move from left to right across buildings with different heights. When the next building is taller, you must use either bricks equal to the height difference or one ladder. With limited bricks and ladders, the goal is to determine the furthest index you can reach.
Approach 1: Greedy with Heap (Priority Queue) (Time: O(n log n), Space: O(n))
This problem rewards a greedy strategy. Ladders should cover the largest climbs while bricks handle smaller ones. Iterate through the array of building heights and compute the difference between consecutive buildings. Whenever you encounter a positive climb, push the difference into a heap and temporarily assume bricks will be used. If total brick usage exceeds the available amount, replace the largest climb with a ladder by removing it from the heap. This effectively assigns ladders to the most expensive climbs.
The heap keeps track of climbs you've encountered so far, allowing you to dynamically decide where ladders provide the most value. This combination of a greedy decision process and a heap (priority queue) makes the solution efficient. As soon as bricks become negative and no ladder can compensate, the current building index is the furthest reachable.
Approach 2: Binary Search on Reachable Distance (Time: O(n log n), Space: O(n))
Another way to think about the problem is to ask: can you reach building k? If you can efficiently validate this, the answer can be found with binary search over the building index range. For each candidate index, compute all height differences up to that point and focus only on positive climbs. Sort or maintain them in a heap so that ladders are used on the largest climbs and bricks cover the remaining ones.
If the required bricks exceed the available supply, the candidate index is not reachable. Binary search narrows the range until the maximum reachable building is identified. This method separates feasibility checking from traversal logic and can be useful when reasoning about constraints or adapting the problem to variations.
Recommended for interviews: The greedy heap solution is what interviewers expect. It demonstrates recognition that ladders should cover the largest climbs and shows comfort with a priority queue to dynamically rebalance decisions. The binary search variant proves you can reframe the problem as a monotonic feasibility check, but the heap-based greedy approach is simpler and more commonly discussed in interviews.
Approach 1: Greedy Approach with Max-Heap
This approach uses a greedy strategy combined with a max-heap (priority queue) to determine the optimal use of bricks and ladders. The idea is to always use bricks first for the smallest height difference and use ladders for the largest, potentially reserving the ladders for future taller buildings. Whenever we encounter a new jump (difference in height), we add it to the heap, and if the total number of jumps exceeds the available ladders, we use bricks for the smallest jump. If we don’t have enough bricks, we can’t proceed further.
import heapq
def furthest_building(heights, bricks, ladders):
min_heap = []
for i in range(len(heights) - 1):
diff = heights[i + 1] - heights[i]
if diff > 0:
heapq.heappush(min_heap, diff)
if len(min_heap) > ladders:
bricks -= heapq.heappop(min_heap)
if bricks < 0:
return i
return len(heights) - 1
# Sample run
heights = [4, 2, 7, 6, 9, 14, 12]
print(furthest_building(heights, 5, 1)) # Output: 4import java.util.PriorityQueue;
public class FurthestBuilding {
public static int furthestBuilding(int[] heights, int bricks, int ladders) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < heights.length - 1; ++i) {
int climb = heights[i + 1] - heights[i];
if (climb > 0) {
minHeap.add(climb);
if (minHeap.size() > ladders) {
bricks -= minHeap.poll();
if (bricks < 0) return i;
}
}
}
return heights.length - 1;
}
public static void main(String[] args) {
int[] heights = {4, 12, 2, 7, 3, 18, 20, 3, 19};
System.out.println(furthestBuilding(heights, 10, 2)); // Output: 7
}
}#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int i = 0; i < heights.size() - 1; ++i) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) {
minHeap.push(diff);
if (minHeap.size() > ladders) {
bricks -= minHeap.top();
minHeap.pop();
if (bricks < 0) return i;
}
}
}
return heights.size() - 1;
}
int main() {
vector<int> heights = {4, 12, 2, 7, 3, 18, 20, 3, 19};
cout << furthestBuilding(heights, 10, 2) << endl; // Output: 7
}function furthestBuilding(heights, bricks, ladders) {
const minHeap = [];
function heapPush(val) {
minHeap.push(val);
minHeap.sort((a, b) => a - b);
}
function heapPop() {
return minHeap.shift();
}
for (let i = 0; i < heights.length - 1; i++) {
let diff = heights[i + 1] - heights[i];
if (diff > 0) {
heapPush(diff);
if (minHeap.length > ladders) {
bricks -= heapPop();
if (bricks < 0) return i;
}
}
}
return heights.length - 1;
}
// Example usage
console.log(furthestBuilding([4, 2, 7, 6, 9, 14, 12], 5, 1)); // Output: 4#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int furthestBuilding(int* heights, int heightsSize, int bricks, int ladders) {
int* diffs = (int*)malloc(heightsSize * sizeof(int));
int diffSize = 0;
for (int i = 0; i < heightsSize - 1; ++i) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) diffs[diffSize++] = diff;
}
qsort(diffs, diffSize, sizeof(int), cmpfunc);
for (int i = 0; i < diffSize && bricks >= 0; ++i) {
if (ladders > 0) {
ladders--;
} else {
bricks -= diffs[i];
if (bricks < 0) return i;
}
}
free(diffs);
return heightsSize - 1;
}
int main() {
int heights[] = {4, 2, 7, 6, 9, 14, 12};
int result = furthestBuilding(heights, 7, 5, 1);
printf("%d\n", result); // Output: 4
return 0;
}using System;
using System.Collections.Generic;
public class FurthestBuilding {
public static int FurthestBuildingMethod(int[] heights, int bricks, int ladders) {
var minHeap = new SortedSet<(int climb, int index)>(Comparer<(int, int)>.Create((x, y) => x.climb == y.climb ? x.index.CompareTo(y.index) : x.climb.CompareTo(y.climb)));
for (int i = 0; i < heights.Length - 1; i++) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) {
minHeap.Add((diff, i));
if (minHeap.Count > ladders) {
bricks -= minHeap.Min.climb;
minHeap.Remove(minHeap.Min);
if (bricks < 0) return i;
}
}
}
return heights.Length - 1;
}
public static void Main() {
int[] heights = { 4, 12, 2, 7, 3, 18, 20, 3, 19 };
Console.WriteLine(FurthestBuildingMethod(heights, 10, 2)); // Output: 7
}
}This Python solution efficiently uses a min-heap to optimize the allocation of ladders and bricks. By storing the smallest height differences, it ensures that the smallest climbs are covered by bricks once ladders run out, similar to priority queue usage in other language solutions.
Time Complexity: O(n log n) due to heapq operations.
Space Complexity: O(n) due to storage of diffs.
Approach 2: Binary Search Approach
This approach employs binary search to find the furthest building we can reach. The binary search is performed over the indices of the buildings (0 to n-1). For each index midpoint in the search, we check if it's possible to reach that building, given the constraints of available bricks and ladders using a helper function that checks feasibility by simulating resource allocation greedily. The search continually refines the possible maximum index based on resource ability.
import heapq
def can_reach(heights, bricks, ladders, target):
min_heap = []
for i in range(target):
diff = heights[i + 1] - heights[i]
if diff > 0:
heapq.heappush(min_heap, diff)
if len(min_heap) > ladders:
bricks -= heapq.heappop(min_heap)
if bricks < 0:
return False
return True
def furthest_building(heights, bricks, ladders):
low, high = 0, len(heights) - 1
result = 0
while low <= high:
mid = (low + high) // 2
if can_reach(heights, bricks, ladders, mid):
result = mid
low = mid + 1
else:
high = mid - 1
return result
# Example usage
heights = [4, 12, 2, 7, 3, 18, 20, 3, 19]
print(furthest_building(heights, 10, 2)) # Output: 7import java.util.PriorityQueue;
public class FurthestBuilding {
private static boolean canReach(int[] heights, int bricks, int ladders, int target) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < target; ++i) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) {
minHeap.add(diff);
if (minHeap.size() > ladders) {
bricks -= minHeap.poll();
if (bricks < 0) return false;
}
}
}
return true;
}
public static int furthestBuilding(int[] heights, int bricks, int ladders) {
int low = 0, high = heights.length - 1, result = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (canReach(heights, bricks, ladders, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] heights = {4, 12, 2, 7, 3, 18, 20, 3, 19};
System.out.println(furthestBuilding(heights, 10, 2)); // Output: 7
}
}#include <iostream>
#include <queue>
using namespace std;
bool canReach(vector<int>& heights, int bricks, int ladders, int target) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int i = 0; i < target; ++i) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) {
minHeap.push(diff);
if (minHeap.size() > ladders) {
bricks -= minHeap.top();
minHeap.pop();
if (bricks < 0) return false;
}
}
}
return true;
}
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
int low = 0, high = heights.size() - 1, result = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (canReach(heights, bricks, ladders, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
int main() {
vector<int> heights = {4, 12, 2, 7, 3, 18, 20, 3, 19};
cout << furthestBuilding(heights, 10, 2) << endl; // Output: 7
}function canReach(heights, bricks, ladders, target) {
const minHeap = [];
function heapPush(val) {
minHeap.push(val);
minHeap.sort((a, b) => a - b);
}
function heapPop() {
return minHeap.shift();
}
for (let i = 0; i < target; i++) {
let diff = heights[i + 1] - heights[i];
if (diff > 0) {
heapPush(diff);
if (minHeap.length > ladders) {
bricks -= heapPop();
if (bricks < 0) return false;
}
}
}
return true;
}
function furthestBuilding(heights, bricks, ladders) {
let low = 0, high = heights.length - 1;
let result = 0;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (canReach(heights, bricks, ladders, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
// Example usage
console.log(furthestBuilding([4, 12, 2, 7, 3, 18, 20, 3, 19], 10, 2)); // Output: 7#include <stdio.h>
#include <stdlib.h>
int canReach(int* heights, int heightsSize, int bricks, int ladders, int target) {
int* minHeap = (int*)malloc(sizeof(int) * heightsSize);
int heapSize = 0;
for (int i = 0; i < target; ++i) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) {
minHeap[heapSize++] = diff;
for (int j = heapSize - 1; j > 0 && minHeap[j] < minHeap[j - 1]; --j) {
int temp = minHeap[j];
minHeap[j] = minHeap[j - 1];
minHeap[j - 1] = temp;
}
if (heapSize > ladders) {
bricks -= minHeap[--heapSize];
if (bricks < 0) {
free(minHeap);
return 0;
}
}
}
}
free(minHeap);
return 1;
}
int furthestBuilding(int* heights, int heightsSize, int bricks, int ladders) {
int low = 0, high = heightsSize - 1, result = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (canReach(heights, heightsSize, bricks, ladders, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
int main() {
int heights[] = {4, 2, 7, 6, 9, 14, 12};
int result = furthestBuilding(heights, 7, 5, 1);
printf("%d\n", result); // Output: 4
return 0;
}using System;
using System.Collections.Generic;
public class FurthestBuilding {
private static bool CanReach(int[] heights, int bricks, int ladders, int target) {
var minHeap = new SortedSet<(int climb, int index)>(Comparer<(int, int)>.Create((x, y) => x.climb == y.climb ? x.index.CompareTo(y.index) : x.climb.CompareTo(y.climb)));
for (int i = 0; i < target; i++) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) {
minHeap.Add((diff, i));
if (minHeap.Count > ladders) {
bricks -= minHeap.Min.climb;
minHeap.Remove(minHeap.Min);
if (bricks < 0) return false;
}
}
}
return true;
}
public static int FurthestBuildingMethod(int[] heights, int bricks, int ladders) {
int low = 0, high = heights.Length - 1, result = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (CanReach(heights, bricks, ladders, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
public static void Main() {
int[] heights = { 4, 12, 2, 7, 3, 18, 20, 3, 19 };
Console.WriteLine(FurthestBuildingMethod(heights, 10, 2)); // Output: 7
}
}Applying binary search in this Python solution effectively searches for the maximum index of reachable buildings using a helper function, can_reach, which factors in available ladders and bricks via a min-heap metaphor. This strategy balances resource usage constraints at each binary search stage.
Time Complexity: O(n log n), resultant of composite binary search logic intertwined with heap operations.
Space Complexity: O(n) owing to priority management.
Approach 3: Default Approach
func furthestBuilding(heights []int, bricks int, ladders int) int {
q := hp{}
n := len(heights)
for i, a := range heights[:n-1] {
b := heights[i+1]
d := b - a
if d > 0 {
heap.Push(&q, d)
if q.Len() > ladders {
bricks -= heap.Pop(&q).(int)
if bricks < 0 {
return i
}
}
}
}
return n - 1
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Max-Heap | Time Complexity: O(n log n) due to heapq operations. |
| Binary Search Approach | Time Complexity: O(n log n), resultant of composite binary search logic intertwined with heap operations. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Heap (Priority Queue) | O(n log n) | O(n) | Best general solution. Efficiently assigns ladders to the largest climbs using a heap. |
| Binary Search + Feasibility Check | O(n log n) | O(n) | Useful when modeling the problem as "can we reach index k" and applying binary search. |
Frequently asked questions
Is Furthest Building You Can Reach easy or hard?
Furthest Building You Can Reach is classified as Medium difficulty on LeetCode with an acceptance rate around 50%. The challenge lies in recognizing the greedy insight that ladders should be reserved for the largest climbs and implementing it efficiently with a heap.
How to solve Furthest Building You Can Reach in O(n)?
A strict O(n) solution is difficult because the algorithm needs to repeatedly identify the largest climb seen so far. Using a heap provides that capability in O(log n) time per operation, leading to an overall O(n log n) complexity. Most optimal interview solutions rely on this heap-based greedy method.
Furthest Building You Can Reach Python or Java solution?
Python solutions typically use the heapq module to manage climbs, while Java implementations rely on PriorityQueue. The algorithm iterates through the height array, pushes positive climbs into the heap, and swaps brick usage with ladders when bricks run out.
What is the best approach for Furthest Building You Can Reach?
The optimal approach uses a greedy strategy with a heap (priority queue). Track every upward climb and always assign ladders to the largest climbs while bricks handle smaller ones. This dynamic reassignment ensures resources are used efficiently. The algorithm runs in O(n log n) time with O(n) space.
What data structure is used in Furthest Building You Can Reach?
The key data structure is a heap (priority queue). It tracks height differences between buildings so the algorithm can quickly choose the largest climb to allocate a ladder. Arrays are used for traversal, while the heap enables efficient greedy decisions.
What is the time complexity of Furthest Building You Can Reach?
The most common solution uses a heap and runs in O(n log n) time because each climb may be inserted or removed from the priority queue. Space complexity is O(n) in the worst case if every step requires tracking a climb.
Is Furthest Building You Can Reach asked at Google, Amazon, or Meta?
Furthest Building You Can Reach appears in interview preparation lists for companies like Google, Amazon, and Meta because it tests greedy decision making with heaps. Candidates must recognize when to reassign limited resources to maximize progress.