Jump Game — reachability, not min jumps

Recognize it from

“From index i you may jump up to a[i] steps forward. Can you reach the last index?” Sometimes they then ask the fewest jumps (Jump Game II). First question is boolean: does a zero trap you.

What it actually does

The greedy fact: you never need to choose a particular jump length. Track reach = the farthest index that any legal standing position can land on. Scan left to right. If the scan index walks past reach, that cell is dead — nothing behind you could jump here, so the rest of the array is unreachable.

This is not a heap of remaining fuel and not DP of min jumps unless they asked for the count. Min jumps (Jump Game II) still uses a greedy window: when i hits the end of the current jump, bump the jump count and open a new window to the farthest seen.

public boolean canJump(int[] a) {
    int reach = 0;
    for (int i = 0; i < a.length; i++) {
        if (i > reach) return false; // this index was never in range of an earlier jump
        reach = Math.max(reach, i + a[i]); // farthest landing from anywhere we could stand
    }
    return true;
}

public boolean canJump(int[] a) {
    int n = a.length;
    if (n <= 1) return true;
    int reach = 0;
    for (int i = 0; i < n && i <= reach; i++) {
        reach = Math.max(reach, i + a[i]);
        if (reach >= n - 1) return true; // early exit: last index is already in range
    }
    return reach >= n - 1;
}

Example 1 — simple

[2, 3, 1, 1, 4] — you can reach the end (for example 0 → 1 → 4).

Answer: true. At i = 1, reach already covers the last index.

Example 2 — every step

[3, 2, 1, 0, 4] — the 0 at index 3 is a wall. maxReach dies there.

Answer: false. The fuel from 3, 2, 1 all expire at index 3. The 4 on the far side is a tease.

Best Time to Buy and Sell — one transaction, running min

Recognize it from

“One buy and one sell later. Max profit, or 0 if you should not trade.” Not unlimited transactions (sum every uphill). Not cooldown / at most k deals — those are a small state machine, still DP.

What it actually does

Profit of a pair (buy day i, sell day j > i) is prices[j] − prices[i]. For a fixed sell day, the best buy is the minimum price strictly before that day. So walk left to right: keep the running minimum, try selling today, then maybe update the minimum.

You never need the whole history, only that one integer. Nested loops make the pair visible; they are O(n²) and not what you type in Live Code.

public int maxProfit(int[] prices) {
    int best = 0;
    for (int i = 0; i < prices.length; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            best = Math.max(best, prices[j] - prices[i]); // buy i, sell j
        }
    }
    return best;
}

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) return 0;
    int minBuy = prices[0]; // cheapest price seen so far is the only buy you need
    int best = 0;
    for (int i = 1; i < prices.length; i++) {
        int p = prices[i];
        best = Math.max(best, p - minBuy); // sell today against that running min
        minBuy = Math.min(minBuy, p); // a new low is a better future buy
    }
    return best;
}

Example 1 — simple

[7, 1, 5, 3, 6, 4]. Buy at 1, sell at 6, profit 5.

Answer: 5.

Example 2 — every step

Long decrease, then a spike: [9, 7, 4, 3, 8]. You must not sell during the slide. The only positive trade is buy 3, sell 8.

Answer: 5. A decreasing prefix never produces a sell. Updating minBuy before computing today’s profit would let you “buy and sell today” for 0 — harmless here, but it hides the “sell against a previous min” rule; compute profit first, then update the min.

When greedy is false — coin change counterexample

Recognize it from

“Fewest coins to make amount.” Greedy (always take the largest coin that fits) is correct for canonical systems like US coins. It is not a theorem for arbitrary coin sets. If you cannot prove no-regret, write DP (unbounded knapsack) or say the counterexample.

What it actually does

Greedy subtracts the largest coin, repeats. Locally that shrinks the remainder fast. Globally it can paint you into leftover 1s that a pair of medium coins would have covered.

The DP is unbounded: dp[a] = fewest coins to make a. For each coin c you may reuse it because dp[a−c] is allowed to already contain c. That is the upward capacity loop — the opposite of 0/1 partition in the DP chapter.

public int coinChangeGreedy(int[] coins, int amount) {
    Arrays.sort(coins); // largest first
    int n = 0, left = amount;
    for (int i = coins.length - 1; i >= 0; i--) {
        int c = coins[i];
        while (left >= c) {
            left -= c;
            n++;
        }
    }
    return left == 0 ? n : -1; // looks right on US coins; not always optimal
}

public int coinChange(int[] coins, int amount) {
    int INF = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0; // zero coins make amount 0
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1); // unbounded: c may already sit inside dp[a-c]
        }
    }
    return dp[amount] >= INF ? -1 : dp[amount];
}

Example 1 — simple

Canonical coins [1, 5, 10], amount 12. Greedy and optimal agree.

Answer: 3 coins (10+1+1). DP also returns 3 (10+1+1, or 5+5+1+1, etc.). Greedy happened to be optimal — that does not prove the next coin set.

Example 2 — every step

Coins [1, 3, 4], amount 6. Greedy: 4+1+1 = 3 coins. Optimal: 3+3 = 2 coins.

Answer: DP 2 (the c=3 transition at a=6). Greedy’s 3 is a lie for this set. Keep this pair in your mouth: “greedy 4+1+1, optimal 3+3.”

See also

Jump reachability and one-transaction stock are the two greeds you can prove in a sentence (running max reach; running min buy). Coin change is the card you use when someone says “greedy is always OK.” Remove-k-digits is stack + greedy — type it from chapter 05, not as a third full dry-run here.