Furthest Building You Can Reach - Practice Coding Problems

Furthest Building You Can Reach - Problem

You are given an integer array heights representing the heights of buildings, along with a certain number of bricks and 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.

Input & Output

Example 1 — Basic Case

$ Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1

› Output: 4

💡 Note: Starting at building 0, we can reach building 4: gaps are -2 (free), +5 (use 5 bricks), -1 (free), +3 (use ladder). At gap +5 to building 5, we need bricks but have none left.

Example 2 — Use All Resources

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

› Output: 7

💡 Note: Use ladders for gaps +8 and +15, use 10 bricks for gaps +5 and +5. Can reach building 7, but gap +16 to building 8 is too large.

Example 3 — All Decreasing

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

› Output: 3

💡 Note: Gap -11 (free), +16 (use 16 bricks), -16 (free). We can reach the end using only bricks for the one upward gap.

Constraints

1 ≤ heights.length ≤ 10⁵
1 ≤ heights[i] ≤ 10⁶
0 ≤ bricks ≤ 10⁶
0 ≤ ladders ≤ heights.length

Visualization

Tap to expand

Understanding the Visualization

Input

Building heights array with limited bricks and ladders

Process

Use greedy strategy: ladders for biggest gaps, bricks for smallest

Output

Maximum building index reachable

Key Takeaway

🎯 Key Insight: Save ladders for the largest gaps by using a min-heap to track optimal resource allocation

Asked in

f Facebook 35 G Google 28 a Amazon 22

The key insight is to use ladders for the largest gaps and bricks for smaller ones. The optimal approach uses a min-heap to dynamically track which gaps should use ladders versus bricks. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Try All Combinations	O(2^n)	O(n)	Recursively try using ladders vs bricks at each gap
Greedy with Min-Heap	O(n log n)	O(n)	Use ladders for largest gaps encountered so far

Try All Combinations — Algorithm Steps

Start from building 0
At each gap, try both ladder and brick options
Track remaining resources and current position
Return maximum reachable position

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at building 0 with full resources

Branch

At each gap, try both ladder and brick options

Result

Return maximum position reached across all paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dfs(int* heights, int size, int i, int remainingBricks, int remainingLadders) {
    if (i == size - 1) {
        return i;
    }
    
    int gap = heights[i + 1] - heights[i];
    if (gap <= 0) {
        return dfs(heights, size, i + 1, remainingBricks, remainingLadders);
    }
    
    int maxReach = i;
    
    // Try using ladder
    if (remainingLadders > 0) {
        int reach = dfs(heights, size, i + 1, remainingBricks, remainingLadders - 1);
        if (reach > maxReach) maxReach = reach;
    }
    
    // Try using bricks
    if (remainingBricks >= gap) {
        int reach = dfs(heights, size, i + 1, remainingBricks - gap, remainingLadders);
        if (reach > maxReach) maxReach = reach;
    }
    
    return maxReach;
}

int solution(int* heights, int size, int bricks, int ladders) {
    return dfs(heights, size, 0, bricks, ladders);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int heights[1000];
    int size = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        heights[size++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int bricks, ladders;
    scanf("%d", &bricks);
    scanf("%d", &ladders);
    
    int result = solution(heights, size, bricks, ladders);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each gap has 2 choices (ladder or bricks), leading to 2^n combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion depth can go up to n levels for the building array

⚡ Linearithmic Space

86.0K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler