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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

Example 2:

1
2
3

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
Example 3:

Example 3:

1
2

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

Solution

This problem is hard such that, we think it is DP related, but even greedy can be applied.

Method 1 - Greedy Using MaxHeap

Ladders should be saved for the largest jumps since they can cover any height difference, making them more valuable. It’s best to use bricks first and only switch to ladders when bricks run out.

If bricks are used on a large jump, we can later swap that usage for a ladder to recover bricks for future steps.

Note that we are looping till n-2, because we are using index i+1 for heights array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int> maxHeap;
        int bricksUsed = 0;
        int n = heights.size();
        for (int i = 0; i < n - 1; ++i) {
            int diff = heights[i + 1] - heights[i];
            if (diff <= 0) continue;
            if (bricksUsed + diff <= bricks) {
                bricksUsed += diff;
                maxHeap.push(diff);
            } else if (ladders > 0) {
                maxHeap.push(diff);
                int maxUsedBricks = maxHeap.top();
                maxHeap.pop();
                bricksUsed += diff - maxUsedBricks;
                ladders--;
            } else {
                return i;
            }
        }
        return n - 1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func furthestBuilding(heights []int, bricks int, ladders int) int {
    h := &MaxHeap{}
    heap.Init(h)
    bricksUsed := 0
    n := len(heights)
    for i := 0; i < n-1; i++ {
        diff := heights[i+1] - heights[i]
        if diff <= 0 {
            continue
        }
        if bricksUsed+diff <= bricks {
            bricksUsed += diff
            heap.Push(h, diff)
        } else if ladders > 0 {
            heap.Push(h, diff)
            maxUsedBricks := heap.Pop(h).(int)
            bricksUsed += diff - maxUsedBricks
            ladders--
        } else {
            return i
        }
    }
    return n - 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
	public int furthestBuilding(int[] heights, int bricks, int ladders) {
	    var pq = new PriorityQueue<Integer>(Collections.reverseOrder());
	    int bricksUsed = 0;
	    int n = heights.length;
	
	    for(int i = 0 ; i < n-1 ; i++){
	        int diff = heights[i+1] - heights[i];
	        
	        // If current height is higher, we don't have to use
	        // bricks or ladder.
	        if(diff <= 0){
	            continue;
	        }
	        
	        // We have to use either brick or ladder.
	        if(diff + bricksUsed <= bricks){
	            // Prefer bricks because we can later change from 
	            // bricks to ladder as we will see below.
	            bricksUsed += diff;
	            pq.add(diff);
	        } else if(ladders > 0){
	            // If even bricks are insufficient, check ladders.
	            // if peek of heap is more than current diff
	            // then remove peek heap, and get back some bricks
		        pq.offer(diff);
		        int maxUsedBricks = pq.peek();
		        
	            bricksUsed += maxUsedBricks - diff;
	                        
	            ladders--;
	        }
	        // Unfortunately, it's not possible to go ahead any further.
	        else return i;
	        
	        
	    }
	    // This is the max we can go ahead.
	    return n-1;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun furthestBuilding(heights: IntArray, bricks: Int, ladders: Int): Int {
        val maxHeap = PriorityQueue<Int>(compareByDescending { it })
        var bricksUsed = 0
        var laddersLeft = ladders
        for (i in 0 until heights.size - 1) {
            val diff = heights[i + 1] - heights[i]
            if (diff <= 0) continue
            if (bricksUsed + diff <= bricks) {
                bricksUsed += diff
                maxHeap.add(diff)
            } else if (laddersLeft > 0) {
                maxHeap.add(diff)
                val maxUsedBricks = maxHeap.poll()
                bricksUsed += diff - maxUsedBricks
                laddersLeft--
            } else {
                return i
            }
        }
        return heights.size - 1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        max_heap = []
        bricks_used = 0
        n = len(heights)
        for i in range(n - 1):
            diff = heights[i + 1] - heights[i]
            if diff <= 0:
                continue
            if bricks_used + diff <= bricks:
                bricks_used += diff
                heapq.heappush(max_heap, -diff)
            elif ladders > 0:
                heapq.heappush(max_heap, -diff)
                max_used_bricks = -heapq.heappop(max_heap)
                bricks_used += diff - max_used_bricks
                ladders -= 1
            else:
                return i
        return n - 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn furthest_building(heights: Vec<i32>, bricks: i32, ladders: i32) -> i32 {
        let mut max_heap = BinaryHeap::new();
        let mut bricks_used = 0;
        let mut ladders_left = ladders;
        let n = heights.len();
        for i in 0..n - 1 {
            let diff = heights[i + 1] - heights[i];
            if diff <= 0 {
                continue;
            }
            if bricks_used + diff <= bricks {
                bricks_used += diff;
                max_heap.push(diff);
            } else if ladders_left > 0 {
                max_heap.push(diff);
                if let Some(max_used_bricks) = max_heap.pop() {
                    bricks_used += diff - max_used_bricks;
                }
                ladders_left -= 1;
            } else {
                return i as i32;
            }
        }
        (n - 1) as i32
    }
}

Complexity

  • ⏰ Time complexity: O(n log n). For each of the n-1 building jumps, you may push or pop from the max-heap, each operation taking O(log n) time.
  • 🧺 Space complexity: O(n). In the worst case, the max-heap can store up to O(n) jump differences.

Method 2 - Greedy Using MinHeap

Let diff be the difference between consecutive building heights. Instead of using a max-heap to reclaim bricks, we can use a min-heap to keep track of the largest k jumps where ladders are used. For each positive diff, add it to the min-heap; if the heap size exceeds the number of ladders, use bricks for the smallest jump by removing it from the heap and subtracting from bricks. If bricks run out (bricks < 0), return the current index; otherwise, if all buildings are reachable, return the last index.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        int n = heights.size();
        for (int i = 0; i < n - 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 n - 1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func furthestBuilding(heights []int, bricks int, ladders int) int {
    h := &MinHeap{}
    heap.Init(h)
    for i := 0; i < len(heights)-1; i++ {
        diff := heights[i+1] - heights[i]
        if diff > 0 {
            heap.Push(h, diff)
        }
        if h.Len() > ladders {
            bricks -= heap.Pop(h).(int)
        }
        if bricks < 0 {
            return i
        }
    }
    return len(heights) - 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	public int furthestBuilding(int[] heights, int bricks, int ladders) {
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for (int i = 0; i < heights.length - 1; i++) {
			int diff = heights[i + 1] - heights[i];
			if (diff > 0) {
				pq.add(d);
			}
			if (pq.size() > ladders) {
				bricks -= pq.poll();
			}
			if (bricks<0) {
				return i;
			}
		}
		return heights.length - 1;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun furthestBuilding(heights: IntArray, bricks: Int, ladders: Int): Int {
        val minHeap = PriorityQueue<Int>()
        var bricksLeft = bricks
        for (i in 0 until heights.size - 1) {
            val diff = heights[i + 1] - heights[i]
            if (diff > 0) {
                minHeap.add(diff)
            }
            if (minHeap.size > ladders) {
                bricksLeft -= minHeap.poll()
            }
            if (bricksLeft < 0) {
                return i
            }
        }
        return heights.size - 1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn furthest_building(heights: Vec<i32>, mut bricks: i32, ladders: i32) -> i32 {
        let mut min_heap = BinaryHeap::new();
        let n = heights.len();
        for i in 0..n - 1 {
            let diff = heights[i + 1] - heights[i];
            if diff > 0 {
                min_heap.push(Reverse(diff));
            }
            if min_heap.len() > ladders as usize {
                if let Some(Reverse(smallest)) = min_heap.pop() {
                    bricks -= smallest;
                }
            }
            if bricks < 0 {
                return i as i32;
            }
        }
        (n - 1) as i32
    }
}

Complexity

  • ⏰ Time complexity: O(n log n). For each of the n-1 jumps, you may push to and pop from the min-heap, each operation taking O(log n) time.
  • 🧺 Space complexity: O(n). The min-heap can also store up to O(n) jump differences in the worst case.