Crack the Backend

Problem Statement

You are given an array heights (building heights), and you have bricks and ladders. You start at building 0 and move to the next. When moving from i to i+1: if heights[i+1] > heights[i], you must use either heights[i+1]-heights[i] bricks or 1 ladder. Return the furthest building index (0-indexed) you can reach.

Key Observations

Greedy: Use ladders for the largest climbs and bricks for the rest. Maintain a min-heap of size at most ladders: store the climb amounts where we "use a ladder". When the heap has more than ladders elements, we must use bricks for the smallest climb in the heap (poll and subtract from bricks). If bricks go negative, we cannot reach the current building — return the previous index.

Approach

High-level: Min-heap for "ladder climbs". For each i: diff = heights[i+1]-heights[i]; if diff<=0 skip; else offer(diff). If heap.size()>ladders then bricks -= heap.poll(); if bricks<0 return i. Return n-1.

Steps: PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int i=0; i<heights.length-1; i++) { int d = heights[i+1]-heights[i]; if (d<=0) continue; pq.offer(d); if (pq.size()>ladders) bricks -= pq.poll(); if (bricks<0) return i; } return heights.length-1;

Implementation

Java

public int furthestBuilding(int[] heights, int bricks, int ladders) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();

    for (int i = 0; i < heights.length - 1; i++) {
        int d = heights[i+1] - heights[i];

        if (d <= 0) {
            continue;
        }

        pq.offer(d);

        if (pq.size() > ladders) {
            bricks -= pq.poll();
        }

        if (bricks < 0) {
            return i;
        }
    }

    return heights.length - 1;
}

Test Cases

Example 1

Input

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

Expected

4

Explanation

Use ladder for 7->6 or 9->14; bricks for rest.

Complexity Analysis

Time: typically O(n log k) or O(n log n).
Space: O(k) or O(n).

Follow-ups

Stream: process one element at a time.