DSA Series: Dynamic Programming (Blind 75, Java)

Overview

• Pattern cheat-sheet
• 1. Climbing Stairs (Easy · LeetCode 70)
• 2. Coin Change (Medium · LeetCode 322)
• 3. Longest Increasing Subsequence (Medium · LeetCode 300)
• 4. Longest Common Subsequence (Medium · LeetCode 1143)
• 5. Word Break (Medium · LeetCode 139)
• 6. Combination Sum (IV) (Medium · LeetCode 377)
• 7. House Robber (Medium · LeetCode 198)
• 8. House Robber II (Medium · LeetCode 213)
• 9. Decode Ways (Medium · LeetCode 91)
• 10. Unique Paths (Medium · LeetCode 62)
• 11. Jump Game (Medium · LeetCode 55)

Part of the DSA Blind 75 series. Track your progress on the Interview Prep page.

Java 11+ solutions for 11 classic DP problems, written for product / fintech interviews (Visa, Mastercard, NPCI, American Express, PayU). Every Java snippet in this file was compiled with javac and checked with assertions against the official examples, edge cases and (where feasible) randomized comparison against a brute-force oracle.

Pattern cheat-sheet

How to identify a DP problem

Ask these questions in order:

1. Is it an optimization / counting / feasibility question? ("minimum number of...", "maximum profit...", "how many ways...", "is it possible to...").
2. Does a greedy choice fail? (Coin Change with coins {1,3,4}, amount 6: greedy gives 4+1+1, optimal is 3+3.)
3. Does the brute-force recursion re-solve the same sub-problem? Draw the recursion tree; if the same arguments appear repeatedly (overlapping sub-problems) and the best answer of a big problem is built from best answers of smaller ones (optimal substructure), it is DP.
4. Are the inputs small enough for a polynomial state space? The number of distinct states (product of parameter ranges) is your time complexity before the per-state transition cost.

Typical phrases: "number of ways", "minimum / maximum", "longest", "can you reach / partition / break", "without choosing adjacent", "subsequence".

The 4-part framework (say this out loud in the interview)

Top-down (memoization) vs bottom-up (tabulation)

Interview workflow: write the brute-force recursion -> add a memo (usually 3 lines) -> convert to a table -> shrink space. Each step is a natural talking point.

Space optimization

• If dp[i] depends only on dp[i-1], dp[i-2] -> keep 2 variables (Climbing Stairs, House Robber, Decode Ways).
• If row i depends only on row i-1 -> keep one or two rows (LCS, Unique Paths). When using one row, iterate in the direction that does not overwrite values still needed (left-to-right for "unbounded" reuse, right-to-left for "use once" 0/1 knapsack).
• You lose the ability to reconstruct the path when you discard the table. Mention this trade-off: to print the answer, keep the full table (or parent pointers), or use Hirschberg's divide and conquer for LCS in O(n) space.

Common DP families seen in this file

Overflow and fintech flavour

Counting problems blow up fast. In a payments interview, "return the answer modulo 1e9+7" or use long / BigInteger is a likely follow-up; use long and reduce with % MOD after every addition.

1. Climbing Stairs (Easy · LeetCode 70)

Problem statement You climb a staircase with n steps. Each move is 1 or 2 steps. Return the number of distinct ways to reach the top.

• n = 2 -> 2 (1+1, 2)
• n = 3 -> 3 (1+1+1, 1+2, 2+1)
• Constraints: 1 <= n <= 45 (so the answer fits in int).

How the interviewer asks / follow-ups

• Disguised: "A customer can pay a bill of n units using instalments of 1 or 2 units. How many distinct instalment schedules exist?" or "A retry policy backs off by 1 or 2 slots; how many retry sequences reach slot n?"
• Follow-ups: (a) steps can be 1..k -> sliding-window sum; (b) n up to 10^18 with answer mod 1e9+7 -> matrix exponentiation / fast doubling on Fibonacci in O(log n); (c) some steps are broken/forbidden -> set dp[i] = 0; (d) print all paths (backtracking, exponential output); (e) cost per step (Min Cost Climbing Stairs).
• Evaluating: do you spot Fibonacci, do you go brute force -> memo -> O(1) space, and can you discuss the log-time follow-up. It is a warm-up; they expect a fast, bug-free answer.

Approach 1: Brute force recursion ways(n) = ways(n-1) + ways(n-2): the last move was a 1-step or a 2-step. Base: ways(1)=1, ways(2)=2. Complexity: O(2^n) time (recursion tree doubles each level; tight bound is O(phi^n)), O(n) stack.

Approach 2: Memoization State = n only, so there are n distinct sub-problems. Cache each. Time O(n), space O(n).

Approach 3: Tabulation dp[i] = ways to reach step i. Dry run for n=5:

Approach 4: O(1) space (final) dp[i] only needs the previous two values -> two variables.

Java code

public class ClimbStairs {
    // Approach 1: plain recursion - O(2^n) time, O(n) stack
    public static int climbRec(int n) {
        if (n <= 2) return n;                       // 1 way for n=1, 2 ways for n=2
        return climbRec(n - 1) + climbRec(n - 2);
    }

    // Approach 2: top-down memoization - O(n) time, O(n) space
    public static int climbMemo(int n) {
        return go(n, new int[n + 1]);
    }
    private static int go(int n, int[] memo) {
        if (n <= 2) return n;
        if (memo[n] != 0) return memo[n];           // 0 == "not computed yet"
        return memo[n] = go(n - 1, memo) + go(n - 2, memo);
    }

    // Approach 3: bottom-up table - O(n) time, O(n) space
    public static int climbTab(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }

    // Approach 4: two variables - O(n) time, O(1) space
    public static int climbOpt(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;                   // ways(1), ways(2)
        for (int i = 3; i <= n; i++) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }

    // Follow-up: may climb 1..k steps at a time. Sliding-window sum, O(n) time, O(n) space.
    public static long climbK(int n, int k) {
        long[] dp = new long[n + 1];
        dp[0] = 1;
        long window = 1;                            // sum of dp[i-k .. i-1]
        for (int i = 1; i <= n; i++) {
            dp[i] = window;
            window += dp[i];
            if (i - k >= 0) window -= dp[i - k];
        }
        return dp[n];
    }
}

Complexity

Edge cases / pitfalls

• n = 1 and n = 2 must be handled before indexing dp[2] (array of size 2 would overflow).
• n = 0: mathematically 1 way (do nothing); constraints exclude it, so state your assumption.
• Overflow: n = 46 already exceeds int; for larger n use long (up to 90) or modulo.
• Naive recursion at n=45 takes seconds - mention it to justify memoization.

Pattern & related problems Fibonacci-style 1-D DP: dp[i] depends on a fixed number of previous states. Related: Min Cost Climbing Stairs (746), House Robber (198), Decode Ways (91), N-th Tribonacci (1137), Fibonacci Number (509), Climbing Stairs with obstacles / k steps (Frog Jump variants).

2. Coin Change (Medium · LeetCode 322)

Problem statement Given coin denominations coins (unlimited supply of each) and a target amount, return the fewest coins that sum to amount, or -1 if impossible.

• coins = [1,2,5], amount = 11 -> 3 (5+5+1)
• coins = [2], amount = 3 -> -1
• coins = [1], amount = 0 -> 0
• Constraints: 1 <= coins.length <= 12, 1 <= coins[i] <= 2^31 - 1, 0 <= amount <= 10^4.

How the interviewer asks / follow-ups

• Disguised: "An ATM holds notes of 100, 200, 500 and 2000. What is the minimum number of notes to dispense Rs. X?" or "A payment gateway splits a settlement into fixed-size batches; minimize the number of batches."
• Follow-ups: (a) print the notes dispensed -> parent array; (b) count the number of ways (Coin Change II, 518) -> dp[a] += dp[a-c] with coins as the outer loop; (c) limited supply of each note (ATM has finite notes) -> bounded knapsack, track counts; (d) when does greedy work? (canonical coin systems such as Indian currency / US coins) and why it fails for {1,3,4}; (e) amount up to 10^9 -> need number theory or BFS on residues; (f) ATM must also keep a fixed note mix.
• Evaluating: recognising that greedy is wrong, clean state definition, initial value (amount+1 as infinity, not Integer.MAX_VALUE which overflows on +1), and the ordering difference between "min coins", "combinations" and "permutations".

Approach 1: Brute force recursion f(rem) = 1 + min(f(rem - c)) over all coins. Try every coin at every level. Time exponential, up to O(n^(amount / minCoin)); stack O(amount / minCoin).

Approach 2: Top-down memoization State = remaining amount rem (0..amount). Cache -1 (impossible) vs a count; use a separate sentinel for "not computed". Time O(amount * n), space O(amount).

Approach 3: Bottom-up tabulation (final) dp[a] = min over coins c<=a of dp[a-c] + 1, dp[0]=0, others initialised to amount+1 ("infinity" that cannot overflow). Dry run for coins=[1,2,5], amount=11:

e.g. dp[11] = min(dp[10], dp[9], dp[6]) + 1 = min(2,3,2)+1 = 3.

(Alternative: BFS over remaining amounts, where the BFS level is the coin count - also O(amount * n).)

Java code

import java.util.*;

public class CoinChange {
    // Approach 1: brute-force recursion - O(S^amount) worst case time, O(amount) stack
    public static int coinChangeRec(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        int best = Integer.MAX_VALUE;
        for (int c : coins) {
            int sub = coinChangeRec(coins, amount - c);
            if (sub >= 0) best = Math.min(best, sub + 1);
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    // Approach 2: top-down memo - O(amount * n) time, O(amount) space
    public static int coinChangeMemo(int[] coins, int amount) {
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, -2);                      // -2 = not computed, -1 = impossible
        return solve(coins, amount, memo);
    }
    private static int solve(int[] coins, int rem, int[] memo) {
        if (rem == 0) return 0;
        if (rem < 0) return -1;
        if (memo[rem] != -2) return memo[rem];
        int best = Integer.MAX_VALUE;
        for (int c : coins) {
            int sub = solve(coins, rem - c, memo);
            if (sub >= 0) best = Math.min(best, sub + 1);
        }
        return memo[rem] = (best == Integer.MAX_VALUE ? -1 : best);
    }

    // Approach 3: bottom-up - O(amount * n) time, O(amount) space
    public static int coinChange(int[] coins, int amount) {
        int INF = amount + 1;                       // larger than any valid answer
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 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);
            }
        }
        return dp[amount] >= INF ? -1 : dp[amount];
    }

    // Follow-up 1: print the coins used (null if impossible)
    public static List<Integer> coinChangePath(int[] coins, int amount) {
        int INF = amount + 1;
        int[] dp = new int[amount + 1];
        int[] last = new int[amount + 1];           // last[a] = coin used to reach a
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a && dp[a - c] + 1 < dp[a]) {
                    dp[a] = dp[a - c] + 1;
                    last[a] = c;
                }
            }
        }
        if (dp[amount] >= INF) return null;
        List<Integer> used = new ArrayList<>();
        for (int a = amount; a > 0; a -= last[a]) used.add(last[a]);
        return used;
    }

    // Follow-up 2 (Coin Change II, LC 518): number of combinations - O(amount * n) time, O(amount) space
    public static int countCombinations(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int c : coins)                         // coins outer => combinations (order ignored)
            for (int a = c; a <= amount; a++)
                dp[a] += dp[a - c];
        return dp[amount];
    }
}

Complexity

Edge cases / pitfalls

• amount = 0 -> 0 (not -1).
• Do not init dp with Integer.MAX_VALUE and then do dp[a-c] + 1 (overflow to negative). Use amount + 1.
• Skip coins larger than the current amount (also avoids negative index). Very large coin values (up to 2^31-1) are why the c <= a check is needed.
• Greedy is wrong in general; do not present it as the solution.
• Loop-order trap: for counting combinations coins must be the outer loop; swapping loops counts permutations (that is Combination Sum IV).
• Duplicate coins in the input are harmless.

Pattern & related problems Unbounded knapsack (min-count variant). Related: Coin Change II (518, count combinations), Combination Sum IV (377, count permutations), Perfect Squares (279), Minimum Cost For Tickets (983), Word Break (139), Partition Equal Subset Sum (416, 0/1 knapsack).

3. Longest Increasing Subsequence (Medium · LeetCode 300)

Problem statement Return the length of the longest strictly increasing subsequence of nums (elements keep their relative order but need not be contiguous).

• [10,9,2,5,3,7,101,18] -> 4 (e.g. [2,3,7,101])
• [0,1,0,3,2,3] -> 4
• [7,7,7,7,7,7,7] -> 1
• Constraints: 1 <= nums.length <= 2500, -10^4 <= nums[i] <= 10^4. Follow-up: O(n log n).

How the interviewer asks / follow-ups

• Disguised: "Given a day-by-day series of transaction amounts for a merchant, find the longest run (not necessarily consecutive days) of strictly growing amounts" or "longest chain of rising stock/ticket prices". Also appears as "Russian Doll Envelopes" / "Box stacking".
• Follow-ups: (a) O(n log n) -> patience sorting with binary search; (b) print the subsequence; (c) count the number of LIS (673); (d) non-strict (non-decreasing) -> use upper bound instead of lower bound; (e) streaming input - the tails array works online; (f) longest bitonic subsequence.
• Evaluating: do you define dp[i] as "ending at i" (not "within first i"), can you reach O(n log n), and do you understand why tails is not itself the LIS.

Approach 1: Brute force recursion (take / skip) At each index either skip it or take it if it is larger than the previously taken element. State is (i, prev). Time O(2^n), space O(n).

Approach 2: DP O(n^2) dp[i] = length of the LIS ending at i = 1 + max(dp[j]) for j < i with nums[j] < nums[i]. Answer = max(dp[i]). (A memoised version of Approach 1 has O(n^2) states (i, prev) and is the same complexity.) Dry run for [10,9,2,5,3,7,101,18]:

Approach 3: Patience sorting / tails array (final), O(n log n) Keep tails[k] = smallest possible last element of an increasing subsequence of length k+1. tails is always sorted, so for each x binary-search the first tails[idx] >= x and overwrite it (or append if none). The length of tails is the answer. Trace:

Length 4. Note [2,3,7,18] happens to be valid here but in general tails is not a real subsequence of the input (e.g. [3,5,1] gives [1,5]).

Java code

import java.util.*;

public class LIS {
    // Approach 1: brute force take / skip - O(2^n) time, O(n) stack
    public static int lisRec(int[] nums) {
        return rec(nums, 0, -1);
    }
    private static int rec(int[] nums, int i, int prev) {
        if (i == nums.length) return 0;
        int skip = rec(nums, i + 1, prev);
        int take = (prev == -1 || nums[i] > nums[prev]) ? 1 + rec(nums, i + 1, i) : 0;
        return Math.max(skip, take);
    }

    // Approach 2: O(n^2) DP - dp[i] = LIS ending exactly at i
    public static int lisQuadratic(int[] nums) {
        int n = nums.length, best = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            best = Math.max(best, dp[i]);
        }
        return best;
    }

    // Approach 3: patience sorting + binary search - O(n log n) time, O(n) space
    public static int lisFast(int[] nums) {
        int[] tails = new int[nums.length];         // tails[k] = smallest tail of an increasing subseq of length k+1
        int size = 0;
        for (int x : nums) {
            int lo = 0, hi = size;                  // first index with tails[idx] >= x
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < x) lo = mid + 1; else hi = mid;
            }
            tails[lo] = x;
            if (lo == size) size++;
        }
        return size;
    }

    // Follow-up: reconstruct one actual LIS - O(n^2) time, O(n) space
    public static List<Integer> lisSequence(int[] nums) {
        int n = nums.length;
        if (n == 0) return new ArrayList<>();
        int[] dp = new int[n], parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);
        int bestEnd = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; parent[i] = j; }
            if (dp[i] > dp[bestEnd]) bestEnd = i;
        }
        LinkedList<Integer> seq = new LinkedList<>();
        for (int i = bestEnd; i != -1; i = parent[i]) seq.addFirst(nums[i]);
        return seq;
    }
}

Complexity

Edge cases / pitfalls

• Strict vs non-strict: strict needs lower bound (first >= x); non-decreasing needs upper bound (first > x). Duplicates ([7,7,7]) -> answer 1 for strict.
• Single element -> 1; empty array (if allowed) -> 0.
• dp[i] means "ending at i" - the answer is the max over all i, not dp[n-1].
• Do not claim tails is the LIS itself.
• Use (lo + hi) >>> 1 to avoid overflow.

Pattern & related problems Subsequence DP / patience sorting. Related: Number of LIS (673), Russian Doll Envelopes (354, sort then LIS), Longest Common Subsequence (1143; LIS = LCS with the sorted distinct array), Maximum Length of Pair Chain (646), Largest Divisible Subset (368), Longest Bitonic Subsequence.

4. Longest Common Subsequence (Medium · LeetCode 1143)

Problem statement Given two strings text1 and text2, return the length of their longest common subsequence (characters in order, not necessarily contiguous), or 0 if none.

• "abcde", "ace" -> 3 ("ace")
• "abc", "abc" -> 3
• "abc", "def" -> 0
• Constraints: 1 <= len <= 1000, lowercase English letters.

How the interviewer asks / follow-ups

• Disguised: "Compare two ledgers / transaction-ID sequences from the bank and the merchant and find the longest set of entries that appear in the same order in both (reconciliation)", "diff two files", "DNA similarity".
• Follow-ups: (a) print the LCS -> backtrack through the table; (b) O(min(m,n)) space (and why you then cannot backtrack; Hirschberg's algorithm); (c) shortest common supersequence (length m + n - LCS); (d) edit distance (72) / minimum deletions to make strings equal (583); (e) longest common substring (reset to 0 on mismatch); (f) LCS of three strings (3-D DP); (g) strings of length 10^5 with a small alphabet - Hunt-Szymanski / bit-parallel.
• Evaluating: 2-D state definition with prefix lengths, correct base row/column, reconstructing the answer, and space reduction.

Approach 1: Brute force recursion lcs(i, j) on prefixes: if last characters match, 1 + lcs(i-1, j-1); else max(lcs(i-1, j), lcs(i, j-1)). Time O(2^(m+n)) in the worst case, stack O(m+n).

Approach 2: Memoization State (i, j) -> m*n states, O(1) each. Time/space O(m*n); recursion depth up to m+n (about 2000, fine for these constraints).

Approach 3: Tabulation dp[i][j] = LCS of the first i chars of text1 and first j chars of text2; row/col 0 are 0. Dry run, text1="abcde" (rows), text2="ace" (cols):

Approach 4: Two rows (final for length-only) Row i only reads row i-1 and itself -> keep two arrays sized by the shorter string. To print the LCS, keep the full table and walk back from dp[m][n]: on a match move diagonally and emit the char, otherwise move toward the larger neighbour.

Java code

import java.util.*;

public class LCS {
    // Approach 1: brute-force recursion - O(2^(m+n)) time, O(m+n) stack
    public static int lcsRec(String a, String b) {
        return rec(a, b, a.length(), b.length());
    }
    private static int rec(String a, String b, int i, int j) {   // LCS of a[0..i), b[0..j)
        if (i == 0 || j == 0) return 0;
        if (a.charAt(i - 1) == b.charAt(j - 1)) return 1 + rec(a, b, i - 1, j - 1);
        return Math.max(rec(a, b, i - 1, j), rec(a, b, i, j - 1));
    }

    // Approach 2: top-down memo - O(m*n) time and space
    public static int lcsMemo(String a, String b) {
        int[][] memo = new int[a.length() + 1][b.length() + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return memo(a, b, a.length(), b.length(), memo);
    }
    private static int memo(String a, String b, int i, int j, int[][] memo) {
        if (i == 0 || j == 0) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int r;
        if (a.charAt(i - 1) == b.charAt(j - 1)) r = 1 + memo(a, b, i - 1, j - 1, memo);
        else r = Math.max(memo(a, b, i - 1, j, memo), memo(a, b, i, j - 1, memo));
        return memo[i][j] = r;
    }

    // Approach 3: bottom-up table - O(m*n) time, O(m*n) space
    public static int lcsTab(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];         // row 0 / col 0 = empty prefix = 0
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? dp[i - 1][j - 1] + 1
                        : Math.max(dp[i - 1][j], dp[i][j - 1]);
        return dp[m][n];
    }

    // Approach 4: two rows - O(m*n) time, O(min(m,n)) space
    public static int lcs(String a, String b) {
        if (b.length() > a.length()) { String t = a; a = b; b = t; }   // make b the shorter one
        int n = b.length();
        int[] prev = new int[n + 1], cur = new int[n + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= n; j++)
                cur[j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? prev[j - 1] + 1
                        : Math.max(prev[j], cur[j - 1]);
            int[] t = prev; prev = cur; cur = t;    // cur[0] stays 0
        }
        return prev[n];
    }

    // Follow-up: print one LCS - O(m*n) time and space
    public static String lcsString(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? dp[i - 1][j - 1] + 1
                        : Math.max(dp[i - 1][j], dp[i][j - 1]);
        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) { sb.append(a.charAt(i - 1)); i--; j--; }
            else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
            else j--;
        }
        return sb.reverse().toString();
    }
}

Complexity

Edge cases / pitfalls

• Off-by-one: with prefix-length indexing, compare charAt(i-1) and charAt(j-1).
• Subsequence != substring (substring resets to 0 on mismatch and tracks a global max).
• Empty string -> 0.
• Multiple valid LCS strings can exist; any one is acceptable unless the interviewer specifies tie-breaking.
• In the rolling-array version, make sure cur[0] stays 0 and swap arrays, not copy.

Pattern & related problems 2-D prefix DP over two sequences. Related: Edit Distance (72), Delete Operation for Two Strings (583), Shortest Common Supersequence (1092), Longest Palindromic Subsequence (516 = LCS of s and reverse(s)), Distinct Subsequences (115), Interleaving String (97), Uncrossed Lines (1035, identical to LCS).

5. Word Break (Medium · LeetCode 139)

Problem statement Given a string s and a dictionary wordDict, return true if s can be split into a space-separated sequence of one or more dictionary words (words may be reused).

• s = "leetcode", dict ["leet","code"] -> true
• s = "applepenapple", dict ["apple","pen"] -> true
• s = "catsandog", dict ["cats","dog","sand","and","cat"] -> false
• Constraints: 1 <= s.length <= 300, 1 <= wordDict.length <= 1000, word length 1..20, all lowercase, dictionary words unique.

How the interviewer asks / follow-ups

• Disguised: "Validate that a concatenated merchant-descriptor / narration string from a card statement can be parsed fully into known tokens (e.g. AMAZONPAYINDIA -> AMAZON PAY INDIA)", "segment a URL / hashtag", "tokenise a UPI note".
• Follow-ups: (a) return all segmentations (Word Break II, 140) - mention exponential output; (b) return one segmentation -> store prevCut[i]; (c) dictionary is huge -> Trie so you stop as soon as no word has this prefix; (d) minimum number of words / fewest unknown characters (Extra Characters in a String, 2707); (e) s is a stream.
• Evaluating: spotting that naive recursion is exponential on "aaaa...ab", memoizing on start index, and bounding the inner loop with the longest word length.

Approach 1: Brute force recursion From start, try every prefix s[start..end); if it is a word, recurse on the rest. Time O(2^n) worst case (string of as with dict {a, aa, aaa,...} ending in an impossible char), stack O(n).

Approach 2: Top-down memo Only n+1 distinct start values. Cache the boolean result per start (use Boolean[] so "unknown" is null). Time O(n^2) substring checks (each O(L) to hash/compare), space O(n).

Approach 3: Bottom-up (final) dp[i] = prefix s[0..i) is segmentable. dp[0]=true. dp[i] = true if some len has dp[i-len] and s[i-len..i) is a word. Limiting len to the longest dictionary word L gives O(n * L) checks. Dry run for "leetcode", dict {leet, code}:

Java code

import java.util.*;

public class WordBreak {
    // Approach 1: brute-force recursion - O(2^n) time worst case (e.g. "aaaa...ab"), O(n) stack
    public static boolean wordBreakRec(String s, List<String> wordDict) {
        return rec(s, 0, new HashSet<>(wordDict));
    }
    private static boolean rec(String s, int start, Set<String> dict) {
        if (start == s.length()) return true;
        for (int end = start + 1; end <= s.length(); end++)
            if (dict.contains(s.substring(start, end)) && rec(s, end, dict)) return true;
        return false;
    }

    // Approach 2: top-down memo - O(n^2) substring checks (x O(L) hashing), O(n) space
    public static boolean wordBreakMemo(String s, List<String> wordDict) {
        return memo(s, 0, new HashSet<>(wordDict), new Boolean[s.length()]);
    }
    private static boolean memo(String s, int start, Set<String> dict, Boolean[] seen) {
        if (start == s.length()) return true;
        if (seen[start] != null) return seen[start];
        for (int end = start + 1; end <= s.length(); end++)
            if (dict.contains(s.substring(start, end)) && memo(s, end, dict, seen))
                return seen[start] = true;
        return seen[start] = false;
    }

    // Approach 3: bottom-up, dp[i] = s[0..i) can be segmented.
    // Only try word lengths up to the longest dictionary word.
    // Time O(n * L * L) (n positions, L lengths, O(L) substring/hash); space O(n + total dict size)
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int maxLen = 0;
        for (String w : dict) maxLen = Math.max(maxLen, w.length());
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int len = 1; len <= Math.min(i, maxLen); len++) {
                if (dp[i - len] && dict.contains(s.substring(i - len, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    // Follow-up (Word Break II, LC 140): return all sentences. Output-sensitive, exponential in worst case.
    public static List<String> wordBreakAll(String s, List<String> wordDict) {
        return all(s, 0, new HashSet<>(wordDict), new HashMap<>());
    }
    private static List<String> all(String s, int start, Set<String> dict, Map<Integer, List<String>> cache) {
        if (cache.containsKey(start)) return cache.get(start);
        List<String> res = new ArrayList<>();
        if (start == s.length()) { res.add(""); return res; }
        for (int end = start + 1; end <= s.length(); end++) {
            String word = s.substring(start, end);
            if (!dict.contains(word)) continue;
            for (String rest : all(s, end, dict, cache))
                res.add(rest.isEmpty() ? word : word + " " + rest);
        }
        cache.put(start, res);
        return res;
    }
}

Complexity

(With L <= 20 and n <= 300 all DP versions are tiny.)

Edge cases / pitfalls

• Put the dictionary in a HashSet - List.contains is O(dict).
• dp[0] = true (empty prefix) is the base case; forgetting it makes everything false.
• Reuse of words is allowed.
• Do not greedily take the longest/shortest prefix: "catsandog" shows greedy fails.
• Word Break II with a memo of full lists can still be exponential - say so.

Pattern & related problems Partition DP over a 1-D string ("unbounded knapsack with strings"). Related: Word Break II (140), Concatenated Words (472), Extra Characters in a String (2707), Palindrome Partitioning (131/132), Coin Change (322), Decode Ways (91), Implement Trie (208).

6. Combination Sum (IV) (Medium · LeetCode 377)

Problem statement Given an array of distinct positive integers nums and a target, return the number of ordered sequences of numbers (reuse allowed) that sum to target. Different orders count as different sequences. The answer is guaranteed to fit in a 32-bit integer.

• nums = [1,2,3], target = 4 -> 7 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1)
• nums = [9], target = 3 -> 0
• Constraints: 1 <= nums.length <= 200, 1 <= nums[i] <= 1000, 1 <= target <= 1000.

How the interviewer asks / follow-ups

• Disguised: "How many different sequences of payments of allowed denominations settle an invoice of Rs. T?" or "how many ordered combinations of fee components add up to T".
• Follow-ups: (a) what if negative numbers are allowed? (infinite sequences possible - must bound the sequence length); (b) count unordered combinations (Coin Change II - swap loops); (c) return the actual sequences (backtracking); (d) answer mod 1e9+7 with long; (e) why the loop order matters.
• Evaluating: do you recognise that "ordered" means permutations -> target in the outer loop, and can you contrast it with Coin Change II.

Approach 1: Brute force recursion count(t) = sum of count(t - x) over all x <= t, count(0) = 1. Time O(n^target), stack O(target).

Approach 2: Memoization State = remaining target. Time O(target * n), space O(target).

Approach 3: Tabulation (final) dp[t] = number of ordered sequences that sum to t. dp[0]=1. Dry run for [1,2,3]:

dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7.

Java code

import java.util.*;

public class CombinationSum4 {
    // Approach 1: brute-force recursion - O(n^target) time, O(target) stack
    public static int combRec(int[] nums, int target) {
        if (target == 0) return 1;
        int ways = 0;
        for (int x : nums)
            if (x <= target) ways += combRec(nums, target - x);
        return ways;
    }

    // Approach 2: top-down memo - O(target * n) time, O(target) space
    public static int combMemo(int[] nums, int target) {
        int[] memo = new int[target + 1];
        Arrays.fill(memo, -1);
        return go(nums, target, memo);
    }
    private static int go(int[] nums, int t, int[] memo) {
        if (t == 0) return 1;
        if (memo[t] != -1) return memo[t];
        int ways = 0;
        for (int x : nums)
            if (x <= t) ways += go(nums, t - x, memo);
        return memo[t] = ways;
    }

    // Approach 3: bottom-up - O(target * n) time, O(target) space
    // Target loop is OUTER => different orders counted as different sequences.
    // int arithmetic wraps on overflow; intermediate wrap is harmless because the true answer fits in int.
    public static int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int t = 1; t <= target; t++)
            for (int x : nums)
                if (x <= t) dp[t] += dp[t - x];
        return dp[target];
    }
}

Complexity

Edge cases / pitfalls

• Loop order: target outer + nums inner -> permutations (this problem). nums outer + target inner -> combinations (Coin Change II). A classic trap.
• Intermediate dp values can overflow int even though the final answer fits; Java wraps (two's complement), so the final result is still correct. With long or % MOD there is no concern. State this explicitly.
• Negative numbers allowed would create infinite answers (e.g. +1 and -1 loop forever) unless sequence length is capped.
• dp[0] = 1 (the empty sequence) is the crucial base case.

Pattern & related problems Unbounded knapsack counting permutations. Related: Coin Change II (518, combinations), Coin Change (322), Climbing Stairs (70; Combination Sum IV with nums = [1,2]), Combination Sum I/II/III (39/40/216, enumerate, not count), Target Sum (494).

7. House Robber (Medium · LeetCode 198)

Problem statement nums[i] is the money in house i on a street. You cannot rob two adjacent houses. Return the maximum amount you can rob.

• [1,2,3,1] -> 4 (houses 0 and 2)
• [2,7,9,3,1] -> 12 (2 + 9 + 1)
• Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 400.

How the interviewer asks / follow-ups

• Disguised: "Pick a set of non-overlapping time slots / non-adjacent batch jobs to maximise settlement value" or "select non-consecutive days to run a promo so that cashback spend is maximised, no two on consecutive days" or "schedule maintenance windows that cannot be back-to-back".
• Follow-ups: (a) circular street (House Robber II); (b) tree street (House Robber III, 337); (c) return which houses; (d) the "adjacency" is k apart; (e) values up to 10^5 houses -> iterative O(1) space.
• Evaluating: a crisp recurrence max(skip, take + two back), O(1) space, and ability to extend to variants.

Approach 1: Brute force recursion At house i: skip -> f(i+1); rob -> nums[i] + f(i+2). Time O(2^n), stack O(n).

Approach 2: Memoization State = index i. Time O(n), space O(n).

Approach 3: Tabulation dp[i] = best for the first i houses; dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]). Dry run, [2,7,9,3,1]:

Approach 4: Two variables (final) Only dp[i-1] and dp[i-2] are used. To print the houses, keep the full table and walk back: if dp[i-1] >= dp[i-2] + nums[i-1] house i-1 was skipped, else it was taken and jump two back.

Java code

import java.util.*;

public class HouseRobber {
    // Approach 1: brute-force recursion (rob or skip house i) - O(2^n) time, O(n) stack
    public static int robRec(int[] nums) {
        return rec(nums, 0);
    }
    private static int rec(int[] nums, int i) {
        if (i >= nums.length) return 0;
        return Math.max(rec(nums, i + 1), nums[i] + rec(nums, i + 2));
    }

    // Approach 2: top-down memo - O(n) time, O(n) space
    public static int robMemo(int[] nums) {
        int[] memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return go(nums, 0, memo);
    }
    private static int go(int[] nums, int i, int[] memo) {
        if (i >= nums.length) return 0;
        if (memo[i] != -1) return memo[i];
        return memo[i] = Math.max(go(nums, i + 1, memo), nums[i] + go(nums, i + 2, memo));
    }

    // Approach 3: bottom-up table - dp[i] = best for first i houses - O(n) time, O(n) space
    public static int robTab(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[1] = n > 0 ? nums[0] : 0;
        for (int i = 2; i <= n; i++)
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        return dp[n];
    }

    // Approach 4: two variables - O(n) time, O(1) space
    public static int rob(int[] nums) {
        int skip = 0, take = 0;                     // best up to previous-previous / previous house
        for (int x : nums) {
            int cur = Math.max(take, skip + x);
            skip = take;
            take = cur;
        }
        return take;
    }

    // Follow-up: which houses? O(n) time and space
    public static List<Integer> robIndices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        if (n > 0) dp[1] = nums[0];
        for (int i = 2; i <= n; i++) dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        LinkedList<Integer> idx = new LinkedList<>();
        int i = n;
        while (i >= 1) {
            if (i >= 2 && dp[i - 1] >= dp[i - 2] + nums[i - 1]) i--;     // house i-1 not robbed
            else { idx.addFirst(i - 1); i -= 2; }                        // robbed house i-1
        }
        return idx;
    }
}

Complexity

Edge cases / pitfalls

• Single house -> nums[0]; empty -> 0.
• Zeros in input are fine.
• Greedy "take the larger of odd/even index sums" or "always take the max house" is wrong ([2,1,1,2] -> 4, rob both ends).
• Make sure skip/take are updated in the right order (use a temp).

Pattern & related problems "Pick or skip with a gap" 1-D DP. Related: House Robber II (213), House Robber III (337), Delete and Earn (740), Maximum Sum of Non-Adjacent Elements, Paint House (256), Climbing Stairs (70).

8. House Robber II (Medium · LeetCode 213)

Problem statement Same as House Robber, but the houses form a circle: the first and last are adjacent. Return the maximum amount.

• [2,3,2] -> 3 (cannot rob houses 0 and 2 together)
• [1,2,3,1] -> 4
• [1,2,3] -> 3
• Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 1000.

How the interviewer asks / follow-ups

• Disguised: "Days of a billing cycle are circular (day 30 is followed by day 1 of the next cycle); choose non-adjacent days to maximise ..." or "ring of regional data centres where neighbours cannot both be scheduled".
• Follow-ups: (a) why it reduces to two linear problems; (b) return the houses; (c) tree version (337); (d) what if the gap is k.
• Evaluating: the reduction insight (the first and last cannot both be chosen -> exclude one of them) and handling n = 1.

Approach 1: Brute force Branch on whether house 0 is robbed: if yes, houses 2..n-2 are available; if no, houses 1..n-1. Recurse linearly inside each. O(2^n) time.

Approach 2: Reduction to two linear problems (final) Either house 0 is not robbed -> solve linear on [1..n-1], or house n-1 is not robbed -> solve linear on [0..n-2]. Answer is the max (the two cases cover all valid selections; the overlap is harmless). Memoised/tabulated linear solver is O(n) time, O(1) space (as in problem 7). Dry run [2,3,2]: range [0..1] -> 3; range [1..2] -> 3; answer 3.

Java code

public class HouseRobber2 {
    // Circle => house 0 and house n-1 are adjacent, so never rob both.
    // Answer = max( best on [0..n-2], best on [1..n-1] ).  O(n) time, O(1) space.
    public static int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];                 // the two ranges below would be empty
        return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
    }

    // Linear House Robber on nums[lo..hi] inclusive
    private static int robLine(int[] nums, int lo, int hi) {
        int skip = 0, take = 0;
        for (int i = lo; i <= hi; i++) {
            int cur = Math.max(take, skip + nums[i]);
            skip = take;
            take = cur;
        }
        return take;
    }

    // Brute force for comparison: recursion with flag "was house 0 robbed" - O(2^n)
    public static int robRec(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        return Math.max(rec(nums, 1, n - 1), nums[0] + rec(nums, 2, n - 2));
    }
    private static int rec(int[] nums, int i, int last) {   // houses i..last
        if (i > last) return 0;
        return Math.max(rec(nums, i + 1, last), nums[i] + rec(nums, i + 2, last));
    }
}

Complexity

Edge cases / pitfalls

• n = 1: the two ranges are empty/overlapping incorrectly; return nums[0] explicitly.
• n = 2: each range has one house -> max(nums[0], nums[1]) (works naturally).
• Do not try to "remove the smaller of first/last" - not valid.
• Verified against a bitmask brute force on random arrays.

Pattern & related problems Break a cycle by fixing/excluding one element. Related: House Robber (198), House Robber III (337), Maximum Sum Circular Subarray (918), Gas Station (134), Paint House II.

9. Decode Ways (Medium · LeetCode 91)

Problem statement A message of letters is encoded with A -> "1", ..., Z -> "26". Given a digit string s, return the number of ways to decode it (0 if none).

• "12" -> 2 (AB, L)
• "226" -> 3 (BZ, VF, BBF)
• "06" -> 0 (a leading zero is invalid)
• Constraints: 1 <= s.length <= 100, digits only, may contain leading zeros. Answer fits in 32 bits.

How the interviewer asks / follow-ups

• Disguised: "A legacy payment-switch message uses numeric field codes 1..26; given a concatenated numeric stream with no delimiters, how many valid interpretations exist?" or "ambiguous ISO-8583-style fields without separators".
• Follow-ups: (a) Decode Ways II (639): * wildcard, answer mod 1e9+7; (b) print all decodings (backtracking); (c) O(1) space; (d) streaming input.
• Evaluating: careful handling of 0 (it only works as part of 10 or 20), the two-way recurrence, and constant space.

Approach 1: Brute force recursion At index i: the single digit s[i] (valid if not '0') and the pair s[i..i+1] (valid if 10..26). Sum the ways from i+1 and i+2. Base: i == n -> 1. Time O(2^n) (Fibonacci-like), stack O(n).

Approach 2: Memoization State = start index. O(n) time, O(n) space.

Approach 3: Tabulation dp[i] = ways to decode the first i chars; dp[0]=1, dp[1] = (s[0] != '0'). For i >= 2: add dp[i-1] if s[i-1] != '0'; add dp[i-2] if s[i-2..i-1] is in 10..26. Dry run for "226":

dp[2]: "2" ok (+dp[1]=1), "22" ok (+dp[0]=1) -> 2. dp[3]: "6" ok (+dp[2]=2), "26" ok (+dp[1]=1) -> 3.

Approach 4: Two variables (final) Same recurrence keeping only dp[i-1] and dp[i-2].

Java code

import java.util.*;

public class DecodeWays {
    // Approach 1: brute-force recursion - O(2^n) time, O(n) stack
    public static int decRec(String s) {
        return s.isEmpty() ? 0 : rec(s, 0);
    }
    private static int rec(String s, int i) {
        if (i == s.length()) return 1;              // consumed everything: one valid decoding
        if (s.charAt(i) == '0') return 0;           // a leading zero can't start a letter
        int ways = rec(s, i + 1);
        if (i + 1 < s.length() && twoDigitOk(s.charAt(i), s.charAt(i + 1))) ways += rec(s, i + 2);
        return ways;
    }
    private static boolean twoDigitOk(char a, char b) {
        int v = (a - '0') * 10 + (b - '0');
        return v >= 10 && v <= 26;
    }

    // Approach 2: top-down memo - O(n) time, O(n) space
    public static int decMemo(String s) {
        if (s.isEmpty()) return 0;
        int[] memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return go(s, 0, memo);
    }
    private static int go(String s, int i, int[] memo) {
        if (i == s.length()) return 1;
        if (s.charAt(i) == '0') return 0;
        if (memo[i] != -1) return memo[i];
        int ways = go(s, i + 1, memo);
        if (i + 1 < s.length() && twoDigitOk(s.charAt(i), s.charAt(i + 1))) ways += go(s, i + 2, memo);
        return memo[i] = ways;
    }

    // Approach 3: bottom-up table, dp[i] = ways to decode first i chars - O(n) time, O(n) space
    public static int decTab(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];                     // single digit 1..9
            if (twoDigitOk(s.charAt(i - 2), s.charAt(i - 1))) dp[i] += dp[i - 2]; // pair 10..26
        }
        return dp[n];
    }

    // Approach 4: O(1) space
    public static int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') return 0;
        int prev2 = 1, prev1 = 1;                   // dp[i-2], dp[i-1]
        for (int i = 2; i <= n; i++) {
            int cur = 0;
            if (s.charAt(i - 1) != '0') cur += prev1;
            if (twoDigitOk(s.charAt(i - 2), s.charAt(i - 1))) cur += prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Complexity

Edge cases / pitfalls

• "0", "06", "100" -> 0; "10", "20" -> 1; "27" -> 1 (only 2|7); "2101" -> 1.
• Two-digit check must be 10..26, not <= 26 (so "06" is not a pair).
• A 0 after a digit other than 1 or 2 makes the whole string undecodable ("30").
• Parse digits via charAt - '0', avoiding Integer.parseInt(substring) allocation in the hot loop.
• Empty string: undefined in the original; return 0 here and say so.

Pattern & related problems 1-D "partition into tokens" DP with fixed token lengths 1 and 2. Related: Decode Ways II (639), Climbing Stairs (70), Word Break (139), Number of Ways to Parse/Split a String, Unique Binary Search Trees.

10. Unique Paths (Medium · LeetCode 62)

Problem statement A robot starts at the top-left cell of an m x n grid and may move only right or down. Return the number of distinct paths to the bottom-right cell.

• m = 3, n = 7 -> 28
• m = 3, n = 2 -> 3 (R-D-D, D-R-D, D-D-R)
• Constraints: 1 <= m, n <= 100; the answer is at most 2 * 10^9 (fits in int).

How the interviewer asks / follow-ups

• Disguised: "Count the routes a transaction can take through an m x n grid of hops/switches (acquirer -> network -> issuer) moving only forward", "paths through a grid of risk checks where some cells (blocked nodes) are down".
• Follow-ups: (a) obstacles (Unique Paths II, 63); (b) minimum-cost path (64); (c) O(n) space; (d) closed-form with combinations and how to compute it without overflow; (e) can also move up/left (then infinite without a no-revisit rule -> a different problem); (f) answer mod 1e9+7 for very large grids (precompute factorials + modular inverse).
• Evaluating: DP recurrence, space optimisation, and spotting the C(m+n-2, m-1) closed form.

Approach 1: Brute force recursion paths(m, n) = paths(m-1, n) + paths(m, n-1); base: a single row or column -> 1. Time O(2^(m+n)), stack O(m+n).

Approach 2: Memoization State (m, n). O(m*n) time and space.

Approach 3: Tabulation dp[i][j] = dp[i-1][j] + dp[i][j-1], first row and column = 1. For 3 x 3:

Approach 4: Single row (space-optimised) dp[j] += dp[j-1] (old dp[j] is "from above", dp[j-1] is "from left"). O(n) space.

Approach 5: Combinatorics (closed form) Every path has m-1 downs and n-1 rights in some order -> C(m+n-2, m-1). Compute with res = res * (total-k+i) / i; each intermediate value is itself a binomial coefficient, so the integer division is exact. Use long to avoid overflow in the product.

Java code

import java.util.*;

public class UniquePaths {
    // Approach 1: brute-force recursion - O(2^(m+n)) time, O(m+n) stack
    public static int pathsRec(int m, int n) {
        if (m == 1 || n == 1) return 1;
        return pathsRec(m - 1, n) + pathsRec(m, n - 1);
    }

    // Approach 2: top-down memo - O(m*n) time and space
    public static int pathsMemo(int m, int n) {
        return go(m, n, new int[m + 1][n + 1]);
    }
    private static int go(int m, int n, int[][] memo) {
        if (m == 1 || n == 1) return 1;
        if (memo[m][n] != 0) return memo[m][n];
        return memo[m][n] = go(m - 1, n, memo) + go(m, n - 1, memo);
    }

    // Approach 3: bottom-up 2D - O(m*n) time, O(m*n) space
    public static int pathsTab(int m, int n) {
        int[][] dp = new int[m][n];
        for (int[] row : dp) Arrays.fill(row, 1);   // first row / first col: only one way
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m - 1][n - 1];
    }

    // Approach 4: single row - O(m*n) time, O(n) space
    public static int pathsRow(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[j] += dp[j - 1];                 // dp[j] (old) = from above, dp[j-1] = from left
        return dp[n - 1];
    }

    // Approach 5: combinatorics C(m+n-2, min(m,n)-1) - O(min(m,n)) time, O(1) space
    public static int pathsMath(int m, int n) {
        int total = m + n - 2, k = Math.min(m, n) - 1;
        long res = 1;
        for (int i = 1; i <= k; i++)
            res = res * (total - k + i) / i;        // always exact: res == C(total-k+i, i)
        return (int) res;
    }

    // Follow-up (Unique Paths II, LC 63): obstacles (1 = blocked) - O(m*n) time, O(n) space
    public static int pathsWithObstacles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) dp[j] = 0;
                else if (j > 0) dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

Complexity

Edge cases / pitfalls

• m = 1 or n = 1 -> 1.
• Division order in the closed form: multiply first, then divide, always in long; dividing earlier breaks exactness.
• Obstacle variant: if the start or end is blocked the answer is 0; blocked cell must reset dp[j] = 0.
• Do not use int for the factorial approach (100! overflows instantly).

Pattern & related problems Grid DP / lattice paths. Related: Unique Paths II (63), Minimum Path Sum (64), Triangle (120), Dungeon Game (174), Cherry Pickup (741), Maximal Square (221).

11. Jump Game (Medium · LeetCode 55)

Problem statement nums[i] is the maximum jump length from index i. Starting at index 0, return true if you can reach the last index.

• [2,3,1,1,4] -> true
• [3,2,1,0,4] -> false (always stuck at index 3)
• Constraints: 1 <= nums.length <= 10^4, 0 <= nums[i] <= 10^5.

How the interviewer asks / follow-ups

• Disguised: "Each checkpoint in a payment-processing pipeline allows you to skip ahead up to nums[i] stages (retries/fallback routes). Can a transaction reach settlement?" or "Each hop of a network can forward up to k hops ahead".
• Follow-ups: (a) minimum number of jumps (Jump Game II, 45); (b) print the path; (c) can jump backwards too (BFS / graph reachability, 1306); (d) why does greedy work; (e) n up to 10^6 -> must be O(n) iterative.
• Evaluating: brute force -> DP -> greedy progression, and a convincing proof of the greedy invariant.

Approach 1: Brute force recursion From i, try every jump length 1..nums[i]. Time O(2^n), stack O(n).

Approach 2: Memoization State i -> can you reach the end from i? Each state tries up to n jumps. Time O(n^2), space O(n).

Approach 3: Bottom-up DP good[i] = from i the end is reachable; good[n-1]=true; good[i] is true if any j in (i, i+nums[i]] is good. Time O(n^2), space O(n).

Approach 4: Greedy (final) Track the farthest index reachable so far. Scan left to right; if the current index exceeds farthest, we are stuck -> false. Update farthest = max(farthest, i + nums[i]). Invariant: every index <= farthest is reachable (there are no holes because you can always jump a shorter distance). Dry run [3,2,1,0,4]: farthest = 3 after i=0, stays 3 through i=3, at i=4 4 > 3 -> false. [2,3,1,1,4]: i=0 -> 2; i=1 -> 4 >= last -> true.

Java code

import java.util.*;

public class JumpGame {
    // Approach 1: brute-force recursion - O(2^n) time, O(n) stack
    public static boolean canJumpRec(int[] nums) {
        return rec(nums, 0);
    }
    private static boolean rec(int[] nums, int i) {
        if (i >= nums.length - 1) return true;
        for (int step = 1; step <= nums[i]; step++)
            if (rec(nums, i + step)) return true;
        return false;
    }

    // Approach 2: top-down memo - O(n^2) time, O(n) space
    public static boolean canJumpMemo(int[] nums) {
        return go(nums, 0, new Boolean[nums.length]);
    }
    private static boolean go(int[] nums, int i, Boolean[] memo) {
        if (i >= nums.length - 1) return true;
        if (memo[i] != null) return memo[i];
        for (int step = 1; step <= nums[i]; step++)
            if (go(nums, i + step, memo)) return memo[i] = true;
        return memo[i] = false;
    }

    // Approach 3: bottom-up DP (good[i] = can reach the end from i) - O(n^2) time, O(n) space
    public static boolean canJumpDp(int[] nums) {
        int n = nums.length;
        boolean[] good = new boolean[n];
        good[n - 1] = true;
        for (int i = n - 2; i >= 0; i--) {
            int far = Math.min(i + nums[i], n - 1);
            for (int j = i + 1; j <= far; j++)
                if (good[j]) { good[i] = true; break; }
        }
        return good[0];
    }

    // Approach 4: greedy farthest reach - O(n) time, O(1) space
    public static boolean canJump(int[] nums) {
        int farthest = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > farthest) return false;         // index i is unreachable
            farthest = Math.max(farthest, i + nums[i]);
            if (farthest >= nums.length - 1) return true;
        }
        return true;
    }

    // Follow-up (Jump Game II, LC 45): minimum jumps, end guaranteed reachable - O(n) time, O(1) space
    public static int minJumps(int[] nums) {
        int jumps = 0, curEnd = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == curEnd) { jumps++; curEnd = farthest; }   // must jump to extend the frontier
        }
        return jumps;
    }
}

Complexity

Edge cases / pitfalls

• [0] -> true (already at the end); [0,1] -> false.
• A zero is only fatal if no earlier jump can cross it.
• Check i > farthest before extending farthest.
• Jump Game II relies on a guaranteed reachable end; loop to n-2 so you do not count an extra jump at the end.
• Memo recursion depth can reach 10^4 -> prefer the greedy or iterative DP for large inputs.

Pattern & related problems DP that collapses to greedy (interval / reachability). Related: Jump Game II (45), Jump Game III (1306), Jump Game VII (1871), Video Stitching (1024), Gas Station (134), Minimum Number of Taps to Open to Water a Garden (1326).