Furthest Building You Can Reach

Find furthest building reachable using optimal allocation of bricks and ladders

Language Selection

Choose your preferred programming language

Showing: Python

Furthest Building You Can Reach

Problem Statement

You are given an integer array heights representing the heights of buildings. You have some number of bricks and ladders.

You start from building 0 and move to the next building by possibly using bricks or ladders.

  • If the current building’s height is greater than or equal to the next building’s height, you do not need bricks or ladders.
  • If the current building’s height is less than the next building’s height, you can either:
    • Use height[i+1] - height[i] bricks, or
    • Use one ladder

Return the furthest building index you can reach (0-indexed).

Input/Output Specifications

  • Input:
    • heights: Array of building heights
    • bricks: Integer representing number of bricks available
    • ladders: Integer representing number of ladders available
  • Output: Integer representing furthest building index reachable

Constraints

  • 1 <= heights.length <= 10^5
  • 1 <= heights[i] <= 10^6
  • 0 <= bricks <= 10^9
  • 0 <= ladders <= heights.length

Examples

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 bricks or ladders.
- Go to building 2 using 5 bricks. You have 0 bricks left.
- Go to building 3 without using bricks or ladders.
- Go to building 4 using 1 ladder. You have 0 ladders left.
- You cannot go beyond building 4 because you have no more bricks or ladders.

Example 2:

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
Explanation: You can reach building 7 optimally.

Example 3:

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
Explanation: You can reach the last building using 17 bricks.

Solution Approaches

Approach 1: Greedy with Min-Heap (Optimal)

Algorithm Explanation:

  1. Use greedy strategy: use ladders for largest height differences
  2. Use min-heap to track height differences where ladders are used
  3. For each positive height difference:
    • If we have ladders, use ladder (add to heap)
    • If heap is full (no more ladders), check if current diff > smallest ladder diff
    • If yes, replace smallest ladder with bricks and use ladder for current
    • If no more bricks available, stop

Implementation:

Python:

import heapq

def furthest_building(heights, bricks, ladders):
    """
    Find furthest building using greedy approach with min-heap
    Time: O(n log n)
    Space: O(n)
    """
    if not heights:
        return 0
    
    min_heap = []  # Track height differences where ladders are used
    
    for i in range(len(heights) - 1):
        diff = heights[i + 1] - heights[i]
        
        if diff <= 0:
            continue  # No resources needed
        
        # Use ladder if available
        if len(min_heap) < ladders:
            heapq.heappush(min_heap, diff)
        else:
            # No ladders available, need to use bricks
            bricks_needed = diff
            
            # If we have ladders used and current diff > smallest ladder diff
            if min_heap and diff > min_heap[0]:
                # Replace ladder with bricks for smallest diff
                bricks_needed = heapq.heappop(min_heap)
                heapq.heappush(min_heap, diff)
            
            # Check if we have enough bricks
            if bricks >= bricks_needed:
                bricks -= bricks_needed
            else:
                return i  # Cannot proceed further
    
    return len(heights) - 1

# Alternative implementation with clearer logic
def furthest_building_v2(heights, bricks, ladders):
    """
    Alternative with explicit resource management
    Time: O(n log n)
    Space: O(n)
    """
    heap = []  # Min-heap for ladder usage
    
    for i in range(len(heights) - 1):
        diff = heights[i + 1] - heights[i]
        
        if diff <= 0:
            continue
        
        heapq.heappush(heap, diff)
        
        # If used more ladders than available
        if len(heap) > ladders:
            # Use bricks for the smallest height difference
            bricks_needed = heapq.heappop(heap)
            if bricks >= bricks_needed:
                bricks -= bricks_needed
            else:
                return i
    
    return len(heights) - 1

Java:

import java.util.*;

class Solution {
    /**
     * Find furthest building using greedy min-heap approach
     * Time: O(n log n)
     * Space: O(n)
     */
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        // Min-heap to track ladder usage
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int i = 0; i < heights.length - 1; i++) {
            int diff = heights[i + 1] - heights[i];
            
            if (diff <= 0) {
                continue;  // No resources needed
            }
            
            minHeap.offer(diff);
            
            // If we've used more ladders than available
            if (minHeap.size() > ladders) {
                // Use bricks for smallest height difference
                int bricksNeeded = minHeap.poll();
                if (bricks >= bricksNeeded) {
                    bricks -= bricksNeeded;
                } else {
                    return i;  // Cannot proceed
                }
            }
        }
        
        return heights.length - 1;
    }
}

Go:

import (
    "container/heap"
)

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[0 : n-1]
    return x
}

// furthestBuilding - Find furthest building using min-heap
// Time: O(n log n), Space: O(n)
func furthestBuilding(heights []int, bricks int, ladders int) int {
    if len(heights) <= 1 {
        return len(heights) - 1
    }
    
    minHeap := &MinHeap{}
    heap.Init(minHeap)
    
    for i := 0; i < len(heights)-1; i++ {
        diff := heights[i+1] - heights[i]
        
        if diff <= 0 {
            continue
        }
        
        heap.Push(minHeap, diff)
        
        // If used more ladders than available
        if minHeap.Len() > ladders {
            bricksNeeded := heap.Pop(minHeap).(int)
            if bricks >= bricksNeeded {
                bricks -= bricksNeeded
            } else {
                return i
            }
        }
    }
    
    return len(heights) - 1
}

JavaScript:

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return min;
    }
    
    size() {
        return this.heap.length;
    }
    
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx] <= this.heap[idx]) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }
    
    bubbleDown() {
        let idx = 0;
        while (2 * idx + 1 < this.heap.length) {
            let minChildIdx = 2 * idx + 1;
            if (2 * idx + 2 < this.heap.length && 
                this.heap[2 * idx + 2] < this.heap[minChildIdx]) {
                minChildIdx = 2 * idx + 2;
            }
            
            if (this.heap[idx] <= this.heap[minChildIdx]) break;
            [this.heap[idx], this.heap[minChildIdx]] = [this.heap[minChildIdx], this.heap[idx]];
            idx = minChildIdx;
        }
    }
}

/**
 * Find furthest building using greedy min-heap approach
 * Time: O(n log n)
 * Space: O(n)
 */
function furthestBuilding(heights, bricks, ladders) {
    const minHeap = new MinHeap();
    
    for (let i = 0; i < heights.length - 1; i++) {
        const diff = heights[i + 1] - heights[i];
        
        if (diff <= 0) continue;
        
        minHeap.push(diff);
        
        // If used more ladders than available
        if (minHeap.size() > ladders) {
            const bricksNeeded = minHeap.pop();
            if (bricks >= bricksNeeded) {
                bricks -= bricksNeeded;
            } else {
                return i;
            }
        }
    }
    
    return heights.length - 1;
}

Key Insights

  • Greedy Strategy: Use ladders for largest height differences (most efficient)
  • Min-Heap Usage: Track smallest height differences where ladders are used
  • Resource Optimization: Replace ladder usage with bricks when beneficial
  • Early Termination: Stop when resources are exhausted

Edge Cases

  1. No Height Increases: All buildings decreasing or same height
  2. Insufficient Resources: Cannot reach second building
  3. No Ladders: Only bricks available
  4. No Bricks: Only ladders available
  5. Single Building: Array of length 1

Test Cases

def test_furthest_building():
    # Example 1
    assert furthest_building([4,2,7,6,9,14,12], 5, 1) == 4
    
    # Example 2  
    assert furthest_building([4,12,2,7,3,18,20,3,19], 10, 2) == 7
    
    # Example 3 - only bricks
    assert furthest_building([14,3,19,3], 17, 0) == 3
    
    # All decreasing
    assert furthest_building([10,8,6,4,2], 0, 0) == 4
    
    # Single building
    assert furthest_building([5], 0, 0) == 0
    
    # Insufficient resources
    assert furthest_building([1,5,1,2,3,4,10,4,6,7,3,1], 4, 1) == 5
    
    print("All tests passed!")

test_furthest_building()

Interview Tips

  1. Resource Optimization: Explain why ladders should be used for largest differences
  2. Greedy Strategy: Justify why this greedy approach works
  3. Heap Choice: Min-heap to track and replace smallest ladder usage
  4. Edge Cases: Handle scenarios with no resources or no obstacles
  5. Alternative Approaches: Could mention binary search + greedy verification

Follow-up Questions

  1. Minimum Resources: Find minimum bricks and ladders needed to reach the end
  2. Multiple Paths: Consider multiple routes between buildings
  3. Resource Costs: Bricks and ladders have different costs
  4. Real-time Decisions: Must decide resource usage immediately
  5. Capacity Constraints: Bricks have weight limits

Common Mistakes

  1. Wrong Greedy Strategy: Using ladders for small differences first
  2. Heap Type: Using max-heap instead of min-heap
  3. Resource Management: Not optimally swapping ladder/brick usage
  4. Edge Cases: Not handling decreasing heights properly
  5. Index Bounds: Off-by-one errors in loop bounds

Concept Explanations

Greedy Optimality: The optimal strategy is to use ladders for the largest height differences because ladders can handle any height difference with the same cost (1 ladder), while bricks cost proportionally to the height difference.

Min-Heap for Optimization: We use a min-heap to track where we’ve used ladders. When we run out of ladders, we check if we can “trade” the ladder used for the smallest height difference (heap root) with bricks to free up a ladder for a larger height difference.

When to Apply: This pattern works for resource allocation problems where you have two types of resources with different cost structures, and you want to optimize their usage. The key insight is using the more flexible resource (ladders) for situations where it provides the most benefit.