Skip to content

1642. Furthest Building You Can Reach 👍

  • Time: $O(|\texttt{heights}|\log \texttt{ladders})$
  • Space: $O(|\texttt{heights}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
    priority_queue<int, vector<int>, greater<int>> minHeap;

    for (int i = 1; i < heights.size(); ++i) {
      const int diff = heights[i] - heights[i - 1];
      if (diff <= 0)
        continue;
      minHeap.push(diff);
      // If we run out of ladders, greedily use as less bricks as possible.
      if (minHeap.size() > ladders)
        bricks -= minHeap.top(), minHeap.pop();
      if (bricks < 0)
        return i - 1;
    }

    return heights.size() - 1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int furthestBuilding(int[] heights, int bricks, int ladders) {
    Queue<Integer> minHeap = new PriorityQueue<>();

    for (int i = 1; i < heights.length; ++i) {
      final int diff = heights[i] - heights[i - 1];
      if (diff <= 0)
        continue;
      minHeap.offer(diff);
      // If we run out of ladders, greedily use as less bricks as possible.
      if (minHeap.size() > ladders)
        bricks -= minHeap.poll();
      if (bricks < 0)
        return i - 1;
    }

    return heights.length - 1;
  }
}

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

    for i, (a, b) in enumerate(itertools.pairwise(heights)):
      diff = b - a
      if diff <= 0:
        continue
      heapq.heappush(minHeap, diff)
      # If we run out of ladders, greedily use as less bricks as possible.
      if len(minHeap) > ladders:
        bricks -= heapq.heappop(minHeap)
      if bricks < 0:
        return i

    return len(heights) - 1