Furthest Building You Can Reach

Furthest Building You Can Reach is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.

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.

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

- 1 <= heights[i] <= 106

- 0 <= bricks <= 109

- 0 <= ladders <= heights.length

Topics and companies

Topics: Array, Greedy, Heap (Priority Queue).

Reported in interviews at Google.

How to practise Furthest Building You Can Reach on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogk) time and O(k) space.

Open Furthest Building You Can Reach in the code editor, or read the Furthest Building You Can Reach editorial for a worked solution with its approach and complexity analysis.

Where Furthest Building You Can Reach sits in the DSA pattern sheet

Problems related to Furthest Building You Can Reach

Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:

Preparing this workspace.