Home/DSA Complete from Scratch to Expert/dsa-topics

Dynamic Programming

Master this topic with zero to advance depth.

Dynamic Programming (DP) Mental Models

Dynamic Programming is an optimization over plain recursion. It is used when a problem can be broken down into subproblems, and these subproblems are solved multiple times. Instead of re-computing, we store the results.

1. The Two Pillars of DP

Overlapping Subproblems: The same subproblems are solved repeatedly (e.g., Fibonacci).
Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions of its subproblems.

2. Implementation Strategies

A. Top-Down (Memoization)

Approach: Recursive + Cache.
Logic: Start from the final goal and break it down. If a subproblem is already solved, return its value from the cache.
Pros: Intuitive, only solves necessary subproblems.

B. Bottom-Up (Tabulation)

Approach: Iterative + Table.
Logic: Start from the smallest subproblems (base cases) and fill the DP table until you reach the target.
Pros: Faster (no recursion overhead), easier to optimize space.

3. Visualizing the Magic

Recursion Tree (Fibonacci):

       f(5)
      /    \
    f(4)    f(3)
   /   \    /   \
 f(3) f(2) f(2) f(1)  <-- f(2) is redundant!

DP Table (Tabulation):

Index: | 0 | 1 | 2 | 3 | 4 | 5 |
Value: | 0 | 1 | 1 | 2 | 3 | 5 |  (dp[i] = dp[i-1] + dp[i-2])

4. Space Optimization

If dp[i] only depends on dp[i-1] and dp[i-2], we don't need a whole array. We can just use two variables! This reduces Space Complexity from O(N) to O(1).

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

Visual Representation

nums = [10, 9, 2, 5, 3, 7, 101, 18]
LIS: [2, 3, 7, 18] or [2, 3, 7, 101]
Length: 4

DP Strategy:
dp[i] = length of LIS ending at index i
dp[i] = 1 + max(dp[j]) for all j < i AND nums[j] < nums[i]

Medium

Examples

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4

Approach 1

Level I: Dynamic Programming (O(N^2))

Intuition

For each element nums[i], we look back at all previous elements nums[j]. If nums[i] > nums[j], then nums[i] can extend the increasing subsequence ending at j.

Thought Process

Initialize dp array where dp[i] = 1 (minimum length is always 1).
For each i from 1 to n-1:
- For each j from 0 to i-1:
  - If nums[i] > nums[j]: dp[i] = max(dp[i], 1 + dp[j]).
Return the maximum value in dp.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

nums = [10, 9, 2, 5]

i	nums[i]	j loop	dp table	Max reached
0	10	-	[1, 1, 1, 1]	1
1	9	j=0 (9<10)	[1, 1, 1, 1]	1
2	2	j=0, 1 (2<9,10)	[1, 1, 1, 1]	1
3	5	j=2 (5>2)	[1, 1, 1, 2]	2

java

import java.util.Arrays;

public class Main {
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int maxLIS = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxLIS = Math.max(maxLIS, dp[i]);
        }
        return maxLIS;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18})); // 4
    }
}

Approach 2

Level II: Memoization (Top-Down DP)

Intuition

The brute force recursive approach recalculates the same subproblems repeatedly. We can cache results using a memo array so that each dp[i] is computed only once.

Thought Process

Initialize memo array with -1.
For solve(i), if memo[i] != -1, return it.
Otherwise, compute dp[i] = 1 + max(solve(j)) for all j < i where nums[j] < nums[i].
memo[i] = dp[i].

Visual

Recursion Tree (with memoization):
solve(7): max over j < 7 where nums[j] < 18
  - solve(6): 2 (cached at step 1)
  - solve(5): 3 (cached at step 2)
  - ... (all others are cached)

⏱ O(N^2)💾 O(N) for cache + recursion stack

Detailed Dry Run

nums = [10, 9, 2, 5]

call	i	j checks	result
1	0	-	1
2	1	j=0 (9<10)=No	1
3	2	j=0,j=1 (2<9,10)=No	1
4	3	j=2 (5>2)	2 (cached!)

java

import java.util.Arrays;

public class Main {
    static int[] memo;
    public static int solve(int[] nums, int i) {
        if (memo[i] != -1) return memo[i];
        memo[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                memo[i] = Math.max(memo[i], 1 + solve(nums, j));
            }
        }
        return memo[i];
    }

    public static int lengthOfLIS(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        int max = 0;
        for (int i = 0; i < nums.length; i++) max = Math.max(max, solve(nums, i));
        return max;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18})); // 4
    }
}

⚠️ Common Pitfalls & Tips

When computing max across all solve(i) calls, don't forget that lru_cache in Python caches the function but the outer max call still needs to iterate all indices.

Approach 3

Level III: Binary Search (O(N log N))

Intuition

This is often called Patience Sorting. We maintain a list tails where tails[i] is the smallest tail of all increasing subsequences of length i+1.

Logic Steps

For each x in nums:
- If x is larger than the largest tail, append it.
- Otherwise, find the smallest tail \ge x using binary search and replace it with x.
The length of tails is the LIS length.

⏱ O(N log N)💾 O(N)

Detailed Dry Run

nums = [10, 9, 2, 5]

x	tails	Action	Reason
10	[10]	Append	List empty
9	[9]	Replace 10	9 is smaller tail for len 1
2	[2]	Replace 9	2 is smaller tail for len 1
5	[2, 5]	Append	5 > 2, starts len 2

java

import java.util.*;

public class Main {
    public static int lengthOfLIS(int[] nums) {
        ArrayList<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            int i = Collections.binarySearch(tails, x);
            if (i < 0) i = -(i + 1);
            if (i == tails.size()) tails.add(x);
            else tails.set(i, x);
        }
        return tails.size();
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18})); // 4
    }
}

⚠️ Common Pitfalls & Tips

The Binary Search approach only gives the length of the LIS, correctly. The tails array itself may NOT represent a valid LIS (e.g., it might be mixed from different subsequences), but its size will always be correct.

Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (grid[0][0]). The robot tries to move to the bottom-right corner (grid[m-1][n-1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Visual Representation

m=3, n=2
Grid:
(S) (1)   (S=Start, E=End)
(1) (1)
(1) (E)

Paths:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
Total: 3

Medium

Examples

Input: m = 3, n = 2
Output: 3
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
Right -> Down -> Down
Down -> Down -> Right
Down -> Right -> Down

Input: m = 3, n = 7
Output: 28

Approach 1

Level I: Dynamic Programming (2D)

Intuition

The number of ways to reach cell (i, j) is the sum of ways to reach the cell above it (i-1, j) and the cell to its left (i, j-1).

Thought Process

dp[i][j] = dp[i-1][j] + dp[i][j-1].
Base cases: dp[0][j] = 1 and dp[i][0] = 1 because there is only one way to move along the edges (straight right or straight down).

⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

m=3, n=3

Row	Col 0	Col 1	Col 2	Action
0	1	1	1	Init Row 0
1	1	2	3	1+1=2, 2+1=3
2	1	3	6	1+2=3, 3+3=6

java

public class Main {
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7)); // 28
    }
}

Approach 2

Level II: Memoization (Top-Down Recursion)

Intuition

The recursive brute force for grid path counting has overlapping subproblems. We cache each (i, j) state so we never recompute it.

Visual

Memo Grid (m=3, n=3):
| 0 | 1 | 1 |
| 1 | 2 | ? |  <- memo[1][2] reused by (2,2)
| 1 | ? | ? |

⏱ O(M * N)💾 O(M * N) memo + O(M+N) stack

Detailed Dry Run

m=3, n=3. memo[2][2] = memo[1][2] + memo[2][1]. Both sub-calls are cached after first computation.

java

public class Main {
    static int[][] memo;
    public static int solve(int m, int n) {
        if (m == 1 || n == 1) return 1;
        if (memo[m][n] != 0) return memo[m][n];
        return memo[m][n] = solve(m - 1, n) + solve(m, n - 1);
    }

    public static int uniquePaths(int m, int n) {
        memo = new int[m + 1][n + 1];
        return solve(m, n);
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7)); // 28
    }
}

Approach 3

Level III: Space Optimized (1D)

Intuition

To compute dp[i][j], we only need the value above it dp[i-1][j] (from the previous row) and the value to its left dp[i][j-1] (already computed in the current row). We can use a single row array.

Logic Steps

Initialize a row array of size n with 1s.
Iterate m-1 times (for all rows except the first).
For each row, iterate through columns 1 to n-1:
- row[j] = row[j] + row[j-1].
Return row[n-1].

⏱ O(M * N)💾 O(N)

Detailed Dry Run

m=3, n=3

Action	row array
Init	[1, 1, 1]
Row 1	[1, (1+1)=2, (2+1)=3]
Row 2	[1, (1+2)=3, (3+3)=6]

java

import java.util.Arrays;

public class Main {
    public static int uniquePaths(int m, int n) {
        int[] row = new int[n];
        Arrays.fill(row, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                row[j] += row[j - 1];
            }
        }
        return row[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 2)); // 3
    }
}

⚠️ Common Pitfalls & Tips

Ensure the loop for columns starts at 1, as the first column always has 1 path (staying at the left edge).

Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Visual Representation

coins = [1, 2, 5], amount = 11

Optimal: 5 + 5 + 1 = 11 (3 coins)

DP Strategy:
To make amount 11, we can take:
- Coin 1: 1 + minCoins(10)
- Coin 2: 1 + minCoins(9)
- Coin 5: 1 + minCoins(6)
We take the minimum of these choices.

Medium

Examples

Input: coins = [1, 2, 5], amount = 11
Output: 3
11 = 5 + 5 + 1

Input: coins = [2], amount = 3
Output: -1

Approach 1

Level I: Brute Force (Recursive)

Intuition

For each coin, we try taking it and then recursively solve for the remaining amount. We try all coins for each state and keep the minimum result.

Thought Process

solve(amt) = 1 + min(solve(amt - coin)) for all coin in coins.
Base cases: If amt == 0, return 0. If amt < 0, return infinity.

Pattern Identification

This is Recursive Exhaustive Search. It explores many redundant paths (e.g., to reach amount 5, you might do 2+2+1, 2+1+2, 1+2+2, etc.).

⏱ O(S^n) where S is amount and n is number of coins💾 O(S) for recursion depth

Detailed Dry Run

coins=[1, 2], amt=3

Call	amt	Choices	Returns
1	3	1+f(2), 1+f(1)	min(2, 2) = 2
2	2	1+f(1), 1+f(0)	min(2, 1) = 1
3	1	1+f(0), 1+f(-1)	min(1, inf) = 1
4	0	-	0 (Base Case)

java

public class Main {
    public static int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return 100000; // Represent Infinity

        int minCoins = 100000;
        for (int coin : coins) {
            int res = coinChange(coins, amount - coin);
            if (res != 100000) {
                minCoins = Math.min(minCoins, 1 + res);
            }
        }
        return minCoins;
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int res = coinChange(coins, 11);
        System.out.println(res >= 100000 ? -1 : res);
    }
}

Approach 2

Level II: Top-Down DP (Memoization)

Intuition

The brute-force recursion recalculates the same amount values repeatedly. We store results in a memo map/array to skip recomputation.

Visual

coins=[1,2], amount=4
tree (without memo):           | with memo:
         f(4)                  | f(4) calls f(3), f(2)
        /    \                | f(3) already done in f(4)!
     f(3)    f(2)              | Skipped!
     / \    / \              |
  f(2) f(1) f(1) f(0)          |

⏱ O(Amount * n)💾 O(Amount)

Detailed Dry Run

coins=[1,2], amount=3. memo[2] = min(1+memo[1], 1+memo[0]) = 1. memo[3] = min(1+memo[2], 1+memo[1]) = 2.

java

import java.util.*;

public class Main {
    static int[] memo;
    public static int solve(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        if (memo[amount] != Integer.MAX_VALUE) return memo[amount];
        int minCoins = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = solve(coins, amount - coin);
            if (res != -1) minCoins = Math.min(minCoins, res + 1);
        }
        return memo[amount] = (minCoins == Integer.MAX_VALUE ? -1 : minCoins);
    }

    public static int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo, Integer.MAX_VALUE);
        return solve(coins, amount);
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11)); // 3
    }
}

⚠️ Common Pitfalls & Tips

Use a sentinel value (not -1) to differentiate 'not computed yet' from 'impossible'. Using -2 or INT_MAX as the uncomputed signal works well.

Approach 3

Level III: Optimal (Bottom-Up DP)

Intuition

Thought Process

We build the solution for all amounts from 1 to targetAmount. For each amount i, we check which coin was the last one added. The minimum coins for i will be 1 + dp[i - coin].

Logic Steps

Initialize a dp array of size amount + 1 with a large value (e.g., amount + 1).
Set dp[0] = 0 (base case).
Loop through each amount i from 1 to amount.
For each i, loop through each coin.
If i - coin >= 0, update dp[i] = min(dp[i], 1 + dp[i - coin]).
Return dp[amount] or -1 if unreachable.

⏱ O(Amount * n) where n is number of coins💾 O(Amount)

Detailed Dry Run

coins = [1, 2, 5], amount = 5

i	Coins Loop	dp[i] calculation	Result
1	1	1 + dp[0] = 1	1
2	1, 2	min(1+dp[1], 1+dp[0])	1
3	1, 2	min(1+dp[2], 1+dp[1])	2
4	1, 2	min(1+dp[3], 1+dp[2])	2
5	1, 2, 5	min(1+dp[4], 1+dp[3], 1+dp[0])	1

java

import java.util.Arrays;

public class Main {
    public static int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11)); // 3
    }
}

⚠️ Common Pitfalls & Tips

Be very careful with the initialization of the dp array. Using Integer.MAX_VALUE in Java or 1e9 can cause integer overflow when you do 1 + dp[i-coin]. Using amount + 1 is a safer 'infinity' for this problem.

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Visual Representation

nums = [1, 2, 3, 1]

Choice 1: Rob House 0 (1) + House 2 (3) = 4
Choice 2: Rob House 1 (2) + House 3 (1) = 3
Result: 4

DP Decision:
At each house, you have two choices:
1. Rob this house: nums[i] + maxLoot from houses (i-2)
2. Skip this house: maxLoot from houses (i-1)

Medium

Examples

Input: nums = [1, 2, 3, 1]
Output: 4
Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount = 1 + 3 = 4.

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount = 2 + 9 + 1 = 12.

Approach 1

Level I: Brute Force (Recursive)

Intuition

For each house, we decide whether to rob it or skip it. If we rob it, we cannot rob the next house. If we skip it, we can rob the next house. We explore both paths and take the maximum.

Thought Process

rob(i) = max(nums[i] + rob(i-2), rob(i-1)).
Base cases: If index is out of bounds, return 0.

Pattern Identification

This is a Decision Based Recursion. It has many overlapping subproblems (e.g., rob(3) calls rob(1) and rob(2), and rob(2) also calls rob(1)).

⏱ O(2^n)💾 O(n) due to recursion stack

Detailed Dry Run

nums = [1, 2, 3]

Call	i	Returns	Action
1	2	max(3+f(0), f(1))	Recurse
2	0	1	Base case
3	1	max(2+f(-1), f(0))	Recurse
4	-1	0	Base case

java

public class Main {
    public static int rob(int[] nums, int i) {
        if (i < 0) return 0;
        // Decision: Rob current house + houses (i-2) OR skip current and take houses (i-1)
        return Math.max(nums[i] + rob(nums, i - 2), rob(nums, i - 1));
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("Max Loot: " + rob(nums, nums.length - 1));
    }
}

Approach 2

Level II: Memoization (Top-Down)

Intuition

We cache the result of rob(i) so that each house is only evaluated once, eliminating the exponential redundancy.

Visual

nums = [1, 2, 3, 1]
Call Tree (Memoized):
rob(3) -> max(1 + rob(1), rob(2))
rob(2) -> max(3 + rob(0), rob(1))   | memo[2] = 4
rob(1) -> max(2 + rob(-1), rob(0)) | memo[1] = 2
rob(0) -> 1 (Base Case)

⏱ O(N)💾 O(N)

Detailed Dry Run

nums = [2, 7, 9]. rob(2) = max(9+rob(0), rob(1)) = max(9+2, 7) = 11. Cached!

java

import java.util.*;

public class Main {
    static Map<Integer, Integer> memo = new HashMap<>();
    public static int rob(int[] nums, int i) {
        if (i < 0) return 0;
        if (memo.containsKey(i)) return memo.get(i);
        int result = Math.max(nums[i] + rob(nums, i - 2), rob(nums, i - 1));
        memo.put(i, result);
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println(rob(nums, nums.length - 1)); // 12
    }
}

⚠️ Common Pitfalls & Tips

Unlike the brute force, memoization ensures O(N) time. But due to the call stack, very long arrays could cause stack overflow — prefer the iterative DP for production.

Approach 3

Level III: Optimal (DP + Space Optimized)

Intuition

Thought Process

We only need the results of the two previous houses to decide for the current one. Instead of an array, we use rob1 (max loot excluding adjacent) and rob2 (max loot including adjacent).

Logic Steps

Initialize rob1 = 0 and rob2 = 0.
Iterate through each house n in nums.
temp = max(n + rob1, rob2).
rob1 = rob2.
rob2 = temp.
Return rob2.

⏱ O(n)💾 O(1)

Detailed Dry Run

nums = [1, 2, 3, 1]

i	n	rob1	rob2	Action
-	-	0	0	Init
0	1	0	1	max(1+0, 0)
1	2	1	2	max(2+0, 1)
2	3	2	4	max(3+1, 2)
3	1	4	4	max(1+2, 4)

java

public class Main {
    public static int rob(int[] nums) {
        int rob1 = 0, rob2 = 0;
        // [rob1, rob2, n, n+1, ...]
        for (int n : nums) {
            int temp = Math.max(n + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("Max loot: " + rob(nums));
    }
}

⚠️ Common Pitfalls & Tips

Ensure rob1 and rob2 are updated correctly in each iteration. rob1 should always be the max loot excluding the house immediately before the current one.

House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Visual Representation

nums = [2, 3, 2]

Circle Layout:
  (2) -- (3)
   |      |
  ( ) -- (2)

Options:
1. Rob House 0: Cannot rob House 1 or House 2. Result: 2
2. Rob House 1: Cannot rob House 0 or House 2. Result: 3
Result: 3

Medium

Examples

Input: nums = [2, 3, 2]
Output: 3
You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Input: nums = [1, 2, 3, 1]
Output: 4

Approach 1

Level I: Brute Force (Recursion)

Intuition

To handle the circular constraint, we can either rob the first house (forcing us to skip the last) or skip the first house (allowing us to potentially rob the last). We run two separate recursions and compare results.

Thought Process

rob(nums, start, end) is a recursive function for a linear range.
In circular nums[0...n-1]:
- Option 1: Rob from 0 to n-2.
- Option 2: Rob from 1 to n-1.
Return max(Option 1, Option 2).

Pattern Identification

Circular to Linear Reduction using Recursion.

⏱ O(2^N)💾 O(N)

Detailed Dry Run

nums = [2, 3, 2]

solve(0, 1): max(2+f(-1), f(0)) = 2. Skip last house.
solve(1, 2): max(2+f(0), f(1)) = 2. Skip first house. Result: 2

java

public class Main {
    private static int robLinear(int[] nums, int i, int start) {
        if (i < start) return 0;
        return Math.max(nums[i] + robLinear(nums, i - 2, start), robLinear(nums, i - 1, start));
    }

    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int n = nums.length;
        return Math.max(robLinear(nums, n - 2, 0), robLinear(nums, n - 1, 1));
    }

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 3, 2}));
    }
}

Approach 2

Level II: Top-Down DP with Helper

Intuition

We reduce the circular problem into two linear House Robber I problems (skip first house or skip last house) and apply memoization on each.

Visual

nums = [2, 3, 2]

Case 1: Skip last -> rob [2, 3] -> memoized linear rob
Case 2: Skip first -> rob [3, 2] -> memoized linear rob
Result: max(3, 3) = 3

⏱ O(N)💾 O(N)

Detailed Dry Run

Call memoized robLinear on [2, 3] → 3. Call memoized robLinear on [3, 2] → 3. max = 3.

java

import java.util.*;

public class Main {
    private static int robLinearMemo(int[] nums, int start, int end, Map<Integer, Integer> memo) {
        if (start > end) return 0;
        if (memo.containsKey(end)) return memo.get(end);
        int res = Math.max(nums[end] + robLinearMemo(nums, start, end - 2, memo),
                           robLinearMemo(nums, start, end - 1, memo));
        memo.put(end, res);
        return res;
    }

    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int n = nums.length;
        return Math.max(robLinearMemo(nums, 0, n - 2, new HashMap<>()),
                        robLinearMemo(nums, 1, n - 1, new HashMap<>()));
    }

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 3, 2})); // 3
    }
}

⚠️ Common Pitfalls & Tips

Since lru_cache in Python captures closure variables, use tuples as arguments for the circular-to-linear reduction to avoid cache collisions between the two sub-problems.

Approach 3

Level III: Dynamic Programming (Linear Sub-problems)

Intuition

The circular constraint means we can either rob the first house OR the last house, but never both. This simplifies the circular problem into two linear House Robber problems:

Rob houses from index 0 to n-2 (exclude last).
Rob houses from index 1 to n-1 (exclude first).

Thought Process

If n=1, return nums[0].
Calculate maxLoot1 = houseRobberLinear(nums[0...n-2]).
Calculate maxLoot2 = houseRobberLinear(nums[1...n-1]).
Return max(maxLoot1, maxLoot2).

Pattern Identification

This is Reducing Circular to Linear. We reuse the standard House Robber logic twice.

⏱ O(N)💾 O(1)

Detailed Dry Run

nums = [2, 3, 2]

Step	Subset	Max Loot (Linear)
1	[2, 3]	max(2, 3) = 3
2	[3, 2]	max(3, 2) = 3
Final	max(3, 3)	3

java

public class Main {
    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robLinear(nums, 0, nums.length - 2), 
                        robLinear(nums, 1, nums.length - 1));
    }

    private static int robLinear(int[] nums, int start, int end) {
        int rob1 = 0, rob2 = 0;
        for (int i = start; i <= end; i++) {
            int temp = Math.max(nums[i] + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 3, 2})); // 3
    }
}

⚠️ Common Pitfalls & Tips

Don't forget the base case for n=1. If you don't handle it, slicing or indexing might fail. Also, ensure both linear calls exclude at least one house to break the circular dependency.

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Visual Representation

nums = [2, 3, 1, 1, 4]

Index: 0  1  2  3  4
Value: 2  3  1  1  4

- From 0 (2): Can jump to 1 or 2.
- From 1 (3): Can jump to 2, 3, or 4 (Goal!).
Result: True

Medium

Examples

Input: nums = [2, 3, 1, 1, 4]
Output: true
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [3, 2, 1, 0, 4]
Output: false
You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Approach 1

Level I: Dynamic Programming (Bottom-Up)

Intuition

We can store whether each index is 'reachable' in a DP table. An index i is reachable if there exists some j < i such that j is reachable AND j + nums[j] >= i.

Thought Process

canReach[i] = true if index i is reachable.
canReach[0] = true.
For each i, check all j < i to see if a jump can land on i.

Pattern Identification

This is Linear DP. While effective, it leads to O(N^2) time.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

nums = [2, 3, 1, 0, 4]

i	nums[i]	j loop	canReach table	Status
0	2	-	[T, F, F, F, F]	Start
1	3	j=0 (0+2 >= 1)	[T, T, F, F, F]	OK
2	1	j=0 (0+2 >= 2)	[T, T, T, F, F]	OK
4	4	j=1 (1+3 >= 4)	[T, T, T, T, T]	REACHED

java

public class Main {
    public static boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[nums.length - 1];
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2,3,1,1,4})); // true
    }
}

Approach 2

Level II: Top-Down DP (Memoization)

Intuition

The standard DP approach checks all j < i. We can speed it up by also keeping a track of the farthest reachable index instead of building the full table — but for memoization we cache 'can we reach this index from the start?'.

Visual

nums = [2, 3, 1, 1, 4]
memo[0] = True, memo[1] = ?, memo[2] = ?
- Check: can we reach index 1? From 0, jump 1 or 2. Yes!
- Can we reach index 4? From 1, jump 3. Yes! memo[4] = True.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

nums = [2, 3, 1, 1, 4]. memo[1] = True (from 0). memo[4] = True (from 1). Early exit!

java

import java.util.*;

public class Main {
    static Boolean[] memo;
    static int[] nums;
    public static boolean canReach(int i) {
        if (i == 0) return true;
        if (memo[i] != null) return memo[i];
        for (int j = 0; j < i; j++) {
            if (canReach(j) && j + nums[j] >= i) {
                return memo[i] = true;
            }
        }
        return memo[i] = false;
    }

    public static boolean canJump(int[] input) {
        nums = input;
        memo = new Boolean[nums.length];
        return canReach(nums.length - 1);
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2, 3, 1, 1, 4})); // true
    }
}

⚠️ Common Pitfalls & Tips

The memoized top-down approach is still O(N^2) in the worst case. The Greedy approach is O(N) and should be preferred for large inputs.

Approach 3

Level III: Optimal (Greedy)

Intuition

We don't need to know all ways to reach an index, just the farthest index we can reach. If we can reach index i, we can also reach everything before it.

Logic Steps

Initialize goal = nums.length - 1.
Iterate through the array from right to left.
If i + nums[i] >= goal, then index i can reach the goal. Update the goal = i.
If at the end goal == 0, return true.

⏱ O(N)💾 O(1)

Detailed Dry Run

nums = [2, 3, 1, 1, 4]

i	nums[i]	i + nums[i]	Goal	Update?
4	4	8	4	Init
3	1	4	4	3+1 >= 4 (YES), Goal=3
2	1	3	3	2+1 >= 3 (YES), Goal=2
1	3	4	2	1+3 >= 2 (YES), Goal=1
0	2	2	1	0+2 >= 1 (YES), Goal=0

java

public class Main {
    public static boolean canJump(int[] nums) {
        int goal = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= goal) {
                goal = i;
            }
        }
        return goal == 0;
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2,3,1,1,4})); // true
    }
}

⚠️ Common Pitfalls & Tips

While this problem has a Greedy solution, many similar problems (like Jump Game II) are better solved with DP or BFS. Always check if a greedy choice leads to the global optimum.

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Visual Representation

text1 = "abcde", text2 = "ace"

LCS is "ace", Length = 3

DP Grid Logic:
  - If text1[i] == text2[j]:
      1 + dp[i+1][j+1] (Match!)
  - Else:
      max(dp[i+1][j], dp[i][j+1]) (Skip one char)

Medium

Examples

Input: text1 = "abcde", text2 = "ace"
Output: 3
The longest common subsequence is "ace" and its length is 3.

Input: text1 = "abc", text2 = "abc"
Output: 3

Approach 1

Level I: Brute Force (Recursive)

Intuition

We compare characters of both strings starting from the beginning. If they match, we increment the count and move both pointers. If they don't match, we have two choices: skip a character from text1 or skip a character from text2. We take the maximum of these two paths.

Thought Process

solve(i, j): LCS of text1[i:] and text2[j:].
If text1[i] == text2[j]: 1 + solve(i+1, j+1).
Else: max(solve(i+1, j), solve(i, j+1)).

Pattern Identification

This is Recursive Decision Tree. The time complexity is exponential because it explores the same (i, j) pairs multiple times.

⏱ O(2^(n+m))💾 O(n+m) for recursion stack

Detailed Dry Run

text1="abc", text2="ace"

i	j	Match?	Action	Returns
0	0	'a'=='a' (Yes)	1 + f(1, 1)	1 + 2 = 3
1	1	'b'=='c' (No)	max(f(2, 1), f(1, 2))	max(1, 2) = 2
1	2	'b'=='e' (No)	max(f(2, 2), f(1, 3))	max(1, 0) = 1

java

public class Main {
    public static int lcs(String s1, String s2, int i, int j) {
        if (i == s1.length() || j == s2.length()) return 0;
        if (s1.charAt(i) == s2.charAt(j)) {
            return 1 + lcs(s1, s2, i + 1, j + 1);
        } else {
            return Math.max(lcs(s1, s2, i + 1, j), lcs(s1, s2, i, j + 1));
        }
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace", 0, 0)); // 3
    }
}

Approach 2

Level II: Memoization (Top-Down 2D)

Intuition

The recursive LCS solution re-evaluates the same (i, j) pairs many times. We add a 2D memo table indexed by string positions.

Visual

text1="abc", text2="ace"
Memo table after caching:
     "" 'a' 'c' 'e'
""   0   0   0   0
'a'  0   [3]  -   -  <- solve(0,0)=3 cached!
'b'  0   -   -   -
'c'  0   -   [1]  -

⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

solve(0, 0): 'a'=='a', return 1+solve(1,1). solve(1,1): 'b'!='c', return max(solve(2,1), solve(1,2)).

java

import java.util.*;

public class Main {
    static int[][] memo;
    public static int solve(String s1, String s2, int i, int j) {
        if (i == s1.length() || j == s2.length()) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (s1.charAt(i) == s2.charAt(j)) return memo[i][j] = 1 + solve(s1, s2, i+1, j+1);
        return memo[i][j] = Math.max(solve(s1, s2, i+1, j), solve(s1, s2, i, j+1));
    }

    public static int longestCommonSubsequence(String text1, String text2) {
        memo = new int[text1.length()][text2.length()];
        for (int[] row : memo) Arrays.fill(row, -1);
        return solve(text1, text2, 0, 0);
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace")); // 3
    }
}

⚠️ Common Pitfalls & Tips

Python's lru_cache automatically creates the 2D memo table. In Java, a 2D array initialized with -1 suffices for string indices.

Approach 3

Level III: Optimal (2D DP)

Intuition

Thought Process

We use a 2D grid where dp[i][j] represents the LCS length for text1[i:] and text2[j:]. We fill the grid from the bottom-right towards the top-left (or top-left to bottom-right).

Logic Steps

Initialize a 2D array dp of size (m+1) x (n+1) with 0s.
Iterate through i (text1) and j (text2) in reverse.
If characters match: dp[i][j] = 1 + dp[i+1][j+1].
Else: dp[i][j] = max(dp[i+1][j], dp[i][j+1]).
Return dp[0][0].

⏱ O(N * M) where N, M are lengths of the strings💾 O(N * M)

Detailed Dry Run

text1="abc", text2="ace"

Row (i)	Col (j)	Match?	dp[i][j] calculation	Value
2 (c)	2 (e)	No	max(dp[3][2], dp[2][3])	0
2 (c)	1 (c)	Yes	1 + dp[3][2]	1
1 (b)	1 (c)	No	max(dp[2][1], dp[1][2])	1
0 (a)	0 (a)	Yes	1 + dp[1][1]	3

java

public class Main {
    public static int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        for (int i = text1.length() - 1; i >= 0; i--) {
            for (int j = text2.length() - 1; j >= 0; j--) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = 1 + dp[i + 1][j + 1];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace")); // 3
    }
}

⚠️ Common Pitfalls & Tips

Remember to initialize the dp table with size (n+1) x (m+1) to handle the base cases (empty strings) easily without extra boundary checks.

Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Visual Representation

s = "leetcode", wordDict = ["leet", "code"]

s[0:4] = "leet" (Found!)
s[4:8] = "code" (Found!)
Result: True

DP Strategy:
dp[i] is true if s[0...i] can be segmented.
dp[i] = true if EXISTS j < i such that dp[j] is true AND s[j...i] is in wordDict.

Medium

Examples

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Return true because "leetcode" can be segmented as "leet code".

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Return true because "applepenapple" can be segmented as "apple pen apple".

Approach 1

Level I: Brute Force (Recursion)

Intuition

Try every possible prefix of the string. If a prefix is in the dictionary, recursively check if the remaining suffix can also be segmented into dictionary words.

Thought Process

For a string s, iterate i from 1 to len(s).
If s[0:i] is in wordDict:
- Recursively call canBreak(s[i:]).
Base case: If the remaining string is empty, return true.

⏱ O(2^N)💾 O(N) for recursion stack

Detailed Dry Run

s = "abc", wordDict = ["a", "bc"]

prefix "a" in Dict? Yes. Recurse on "bc".
prefix "b" in Dict? No.
prefix "bc" in Dict? Yes. Recurse on "".
Base case "" -> True.

java

import java.util.*;

public class Main {
    public static boolean wordBreak(String s, List<String> wordDict) {
        if (s.isEmpty()) return true;
        for (int i = 1; i <= s.length(); i++) {
            if (wordDict.contains(s.substring(0, i)) && wordBreak(s.substring(i), wordDict)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(wordBreak("leetcode", Arrays.asList("leet", "code"))); // true
    }
}

Approach 2

Level II: Memoization (Top-Down DP)

Intuition

The brute-force recursion checks all prefixes and re-explores the same suffixes repeatedly. By caching results for each starting index, we eliminate redundant work.

Visual

s = "leetcode", dict = ["leet", "code"]
memo[0]=T -> "leet" matches -> memo[4]=?
memo[4]=T -> "code" matches -> memo[8]=T

⏱ O(N^2 * L)💾 O(N)

Detailed Dry Run

s="catsdog", dict=["cats","dog"]. memo[0]: "cats" -> memo[4]. memo[4]: "dog" -> memo[7]=T. Cached!

java

import java.util.*;

public class Main {
    static Map<Integer, Boolean> memo = new HashMap<>();
    public static boolean solve(String s, Set<String> dict, int i) {
        if (i == s.length()) return true;
        if (memo.containsKey(i)) return memo.get(i);
        for (int j = i + 1; j <= s.length(); j++) {
            if (dict.contains(s.substring(i, j)) && solve(s, dict, j)) {
                memo.put(i, true);
                return true;
            }
        }
        memo.put(i, false);
        return false;
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        return solve(s, new HashSet<>(wordDict), 0);
    }

    public static void main(String[] args) {
        System.out.println(wordBreak("leetcode", Arrays.asList("leet", "code"))); // true
    }
}

⚠️ Common Pitfalls & Tips

Use a Set for dictionary lookups (O(1)) instead of a list (O(L)). Without this, the overall complexity worsens significantly.

Approach 3

Level III: Dynamic Programming (Bottom-Up)

Intuition

We check every possible prefix of the string. If a prefix s[0...j] can be segmented (indicated by dp[j] = true), we then check if the remaining substring s[j...i] exists in the dictionary.

Thought Process

Initialize dp array of size n+1 with false.
dp[0] = true (empty string is always valid).
For i from 1 to n:
- For j from 0 to i-1:
  - If dp[j] is true AND s.substring(j, i) is in wordDict:
    - Set dp[i] = true and break.
Return dp[n].

⏱ O(N^2 * L) where L is max word length💾 O(N)

Detailed Dry Run

s = "leetcode", dict = ["leet", "code"]

i	j	Substring	dp[j]	Solution
0	-	-	T	Base Case
4	0	"leet"	T	dp[4] = True
8	4	"code"	T	dp[8] = True

java

import java.util.*;

public class Main {
    public static boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        Set<String> set = new HashSet<>(wordDict);
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        System.out.println(wordBreak("leetcode", Arrays.asList("leet", "code")));
    }
}

⚠️ Common Pitfalls & Tips

Be careful with substring indexing (inclusive start, exclusive end). Using a Set for dictionary lookup improves lookup time from O(W) to O(1) average.

Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Visual Representation

nums = [1, 5, 11, 5]
Total Sum = 22, Target = 11

Subsets:
[1, 5, 5] -> Sum 11
[11] -> Sum 11
Result: True

Logic:
Can we find a subset with sum equal to (TotalSum / 2)?

Medium

Examples

Input: nums = [1, 5, 11, 5]
Output: true
The array can be partitioned as [1, 5, 5] and [11].

Input: nums = [1, 2, 3, 5]
Output: false

Approach 1

Level I: Dynamic Programming (Bottom-Up 2D)

Intuition

This is a variation of the 0/1 Knapsack Problem. We want to find if there's a subset with sum = totalSum / 2.

Thought Process

If totalSum is odd, return false (cannot partition equally).
Target = totalSum / 2.
dp[i][j] = true if sum j can be formed using first i elements.
dp[i][j] = dp[i-1][j] (exclude current) OR dp[i-1][j - nums[i]] (include current, if j >= nums[i]).

⏱ O(N * Target)💾 O(N * Target)

Detailed Dry Run

nums = [1, 5, 5], Target = 5.5 (Skip, 11 is total) nums = [1, 2, 3], Target = 3

i	x	Sum 0	Sum 1	Sum 2	Sum 3	Action
0	1	T	T	F	F	Init
1	2	T	T	T	T	dp[0][3]
Result					T	True!

java

public class Main {
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        for (int i = 0; i <= nums.length; i++) dp[i][0] = true;

        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) {
                    dp[i][j] = dp[i][j] || dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[nums.length][target];
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 5, 11, 5})); // true
    }
}

Approach 2

Level II: Memoization (Top-Down)

Intuition

The 2D DP bottom-up approach explores the entire grid. A top-down memoized approach explores only the reachable states. Both have the same complexity but memoization is more intuitive to derive.

Visual

nums=[1,5,11,5], target=11
solve(4, 11): can_pick(11)? No, but 11<11 is false for nums[3]=5
solve(3, 6): can_pick(11)? ...

⏱ O(N * Target)💾 O(N * Target)

Detailed Dry Run

nums=[1,5,5,11], target=11. solve(3, 11) = take 11 = solve(2, 0) = True! Cached.

java

import java.util.*;

public class Main {
    static Map<String, Boolean> memo = new HashMap<>();
    public static boolean solve(int[] nums, int i, int target) {
        if (target == 0) return true;
        if (i == 0 || target < 0) return false;
        String key = i + "_" + target;
        if (memo.containsKey(key)) return memo.get(key);
        boolean result = solve(nums, i - 1, target - nums[i - 1]) || solve(nums, i - 1, target);
        memo.put(key, result);
        return result;
    }

    public static boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;
        return solve(nums, nums.length, sum / 2);
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 5, 11, 5})); // true
    }
}

⚠️ Common Pitfalls & Tips

String keys for memoization in C++/Go/Java are slow. A 2D boolean array with i and t as indices is faster and preferred in practice.

Approach 3

Level III: Space Optimized (1D)

Intuition

Since dp[i][j] only depends on the previous row dp[i-1], we can use a single row array. To avoid using the same element twice for the same sum (0/1 constraint), we iterate the sum backwards.

Logic Steps

Initialize a dp array of size target + 1 with false.
dp[0] = true.
For each num in nums:
- For j from target down to num:
  - dp[j] = dp[j] || dp[j - num].

⏱ O(N * Target)💾 O(Target)

Detailed Dry Run

nums = [1, 2, 3], Target = 3

num	Target 3	Target 2	Target 1	Target 0
-	F	F	F	T
1	F	F	T (0+1)	T
2	T (1+2)	T (0+2)	T	T
3	T (0+3)	T	T	T

java

public class Main {
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int n : nums) {
            for (int j = target; j >= n; j--) {
                dp[j] = dp[j] || dp[j - n];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 2, 3, 5})); // false
    }
}

⚠️ Common Pitfalls & Tips

You must iterate the inner loop backwards (from target to num). If you iterate forwards, you might use the same element multiple times for the same sum (which is unbounded knapsack behavior, not 0/1).

Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Visual Representation

n = 3
Ways:
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Total: 3 ways

Recursion Tree:
       (3)
      /   \
    (2)   (1)
   /   \    |
 (1)   (0) (0)

Easy

Examples

Input: n = 2
Output: 2
1 step + 1 step
2 steps

Input: n = 3
Output: 3
1 + 1 + 1
1 + 2
2 + 1

Approach 1

Level I: Brute Force (Recursion)

Intuition

To reach step n, you could have come from either step n-1 (by taking 1 step) or step n-2 (by taking 2 steps). Thus, the total ways $f(n) = f(n-1) + f(n-2)$ . This is exactly the Fibonacci sequence.

Thought Process

Base cases: If $n=0$ or $n=1$ , there is only 1 way.
Recursive step: Return $solve(n-1) + solve(n-2)$ .

Pattern Identification

This is Plain Recursion. The bottleneck is that it re-calculates the same steps many times, leading to an exponential time complexity.

⏱ O(2^n)💾 O(n) due to recursion stack

Detailed Dry Run

Call	n	Returns	Action
1	3	f(2) + f(1)	Recurse
2	2	f(1) + f(0)	Recurse
3	1	1	Base Case
4	0	1	Base Case

java

public class Main {
    public static int climbStairs(int n) {
        if (n <= 1) return 1;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("Ways to climb 3 stairs: " + climbStairs(3)); // 3
    }
}

Approach 2

Level II: Memoization (Top-Down)

Intuition

Cache the result of climb(n) using a memo table so each stair count is computed only once.

Visual

climb(5)
  climb(4) --cached after first call!
  climb(3) --cached after first call!
  ...
Only N unique calls made.

⏱ O(N)💾 O(N)

Detailed Dry Run

climb(4) = climb(3) + climb(2). climb(3) = climb(2) + climb(1). Both branches cache climb(2)=2.

java

import java.util.*;

public class Main {
    static Map<Integer, Integer> memo = new HashMap<>();
    public static int climbStairs(int n) {
        if (n <= 1) return 1;
        if (memo.containsKey(n)) return memo.get(n);
        int result = climbStairs(n - 1) + climbStairs(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(climbStairs(5)); // 8
    }
}

⚠️ Common Pitfalls & Tips

Python's lru_cache handles the caching automatically. In other languages, a HashMap or array of size N+1 is needed.

Approach 3

Level III: Optimal (DP + Space Optimization)

Intuition

Thought Process

Since we only need the last two results ( $f(n-1)$ and $f(n-2)$ ) to calculate the current one, we can use two variables instead of a full DP array. This is the Iterative approach with O(1) Space.

Logic Steps

Initialize prev1 = 1 (for step 1) and prev2 = 1 (for step 0).
Loop from 2 to n.
Calculate current = prev1 + prev2.
Update prev2 = prev1 and prev1 = current.

⏱ O(n)💾 O(1)

Detailed Dry Run

n = 3

i	current	prev1	prev2	Action
-	-	1	1	Init
2	1+1=2	2	1	Update variables
3	2+1=3	3	2	Update variables

java

public class Main {
    public static int climbStairs(int n) {
        if (n <= 1) return 1;
        int prev2 = 1; // n-2
        int prev1 = 1; // n-1
        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        System.out.println("Ways for 5 stairs: " + climbStairs(5)); // 8
    }
}

⚠️ Common Pitfalls & Tips

Be careful with base cases. If $n=0$ is considered 1 way (doing nothing), the logic holds. For $n=1$ , it's also 1 way. The loop should start from 2.

Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for . and * where:

. Matches any single character.
* Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Visual Representation

s = "aa", p = "a*"

- 'a*' can match "", "a", "aa", "aaa", etc.
- Since it matches "aa", result is True.

s = "ab", p = ".*"
- '.*' matches anything. Result is True.

Hard

Examples

Input: s = "aa", p = "a"
Output: false
index 0 matches 'a', but index 1 does not. Pattern is exhausted.

Input: s = "aa", p = "a*"
Output: true

Input: s = "ab", p = ".*"
Output: true

Approach 1

Level I: Brute Force (Recursion)

Intuition

At each step, we check if the first character of the string matches the first character of the pattern. Special handling is needed for '*' which can match zero or more of the preceding element.

Thought Process

If p is empty, return true if s is also empty.
Check if the first characters match (s[0] == p[0] or p[0] == '.').
If p[1] == '*':
- Either skip '*' and preceding char (zero match): isMatch(s, p[2:]).
- Or if first chars match, consume one char of s and keep pattern: first_match && isMatch(s[1:], p).
Else: If first chars match, recurse on isMatch(s[1:], p[1:]).

⏱ Exponential💾 O(N+M) for recursion stack

Detailed Dry Run

s = "aa", p = "a*"

p[1] is '*'. Try skip: isMatch("aa", "") -> False.
Try consume: 'a'=='a', so isMatch("a", "a*").
Again '', try consume: 'a'=='a', so isMatch("", "a").
Again '*', try skip: isMatch("", "") -> True.

java

public class Main {
    public static boolean isMatch(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();
        boolean firstMatch = !s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');

        if (p.length() >= 2 && p.charAt(1) == '*') {
            return (isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p)));
        } else {
            return firstMatch && isMatch(s.substring(1), p.substring(1));
        }
    }

    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a*")); // true
    }
}

Approach 2

Level II: Memoization (Top-Down 2D)

Intuition

The recursive regex matching recalculates many overlapping (i, j) states. Adding a 2D memo array indexed by (si, pi) eliminates repeated work.

Visual

s="aa", p="a*"
solve(0,0): p[1]='*' -> zero match: solve(0,2); one+ match: solve(1,0)
solve(1,0): cached after first call!

⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

s="aa", p="a*". memo[0][0]: p[1]='*', try zero: memo[0][2]=T (empty matches empty). Return True.

java

import java.util.*;

public class Main {
    static Integer[][] memo;
    static String s, p;
    public static int solve(int si, int pi) {
        if (pi == p.length()) return si == s.length() ? 1 : 0;
        if (memo[si][pi] != null) return memo[si][pi];
        boolean firstMatch = si < s.length() && (p.charAt(pi) == s.charAt(si) || p.charAt(pi) == '.');
        int res;
        if (pi + 1 < p.length() && p.charAt(pi + 1) == '*') {
            res = (solve(si, pi + 2) == 1 || (firstMatch && solve(si + 1, pi) == 1)) ? 1 : 0;
        } else {
            res = (firstMatch && solve(si + 1, pi + 1) == 1) ? 1 : 0;
        }
        return memo[si][pi] = res;
    }

    public static boolean isMatch(String str, String pattern) {
        s = str; p = pattern;
        memo = new Integer[s.length() + 1][p.length() + 1];
        return solve(0, 0) == 1;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a*")); // true
    }
}

⚠️ Common Pitfalls & Tips

The '*' operator makes regex DP tricky. Always first try the 'zero match' path (pi+2), then only try 'one+ match' if firstMatch is true to avoid infinite loops.

Approach 3

Level III: Dynamic Programming (Bottom-Up 2D)

Intuition

We use a 2D table dp[i][j] to represent if s[0...i-1] matches p[0...j-1].

Thought Process

dp[0][0] = true (empty string matches empty pattern).
Pattern with '*':
- Case 1: '*' matches zero characters: dp[i][j] = dp[i][j-2].
- Case 2: '*' matches one or more: dp[i][j] = dp[i-1][j] if s[i-1] matches p[j-2].
Pattern without '*':
- If s[i-1] matches p[j-1] (either same char or '.'), dp[i][j] = dp[i-1][j-1].

⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

s = "aa", p = "a*"

i\j	""	'a'	'*'
""	T	F	T (zero 'a')
'a'	F	T	T (one 'a')
'a'	F	F	T (two 'a')

java

public class Main {
    public static boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        for (int j = 2; j <= p.length(); j++) {
            if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
        }

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.') {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[s.length()][p.length()];
    }

    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a*")); // true
    }
}

⚠️ Common Pitfalls & Tips

Handling the empty string base case for patterns like a*b*c* is tricky. Ensure you initialize dp[0][j] correctly for '*' characters.

Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it, represented by an array nums. You are asked to burst all the balloons.

If you burst the i-th balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. After bursting it, the i - 1-th and i + 1-th balloons become adjacent.

Find the maximum coins you can collect by bursting the balloons wisely. (Assume nums[-1] = nums[n] = 1).

Visual Representation

nums = [3, 1, 5, 8]

Add boundary: [1, 3, 1, 5, 8, 1]

If we burst 1 first:
Coins = 3 * 1 * 5 = 15
Remaining: [1, 3, 5, 8, 1]

Wait! It's better to think: "Which balloon is burst LAST in range (i, j)?"

Hard

Examples

Input: nums = [3, 1, 5, 8]
Output: 167
nums = [3,1,5,8] -> [3,5,8] -> [3,8] -> [8] -> []
coins = 315 + 358 + 138 + 181 = 15 + 120 + 24 + 8 = 167

Input: nums = [1, 5]
Output: 10

Approach 1

Level I: Brute Force (Recursion)

Intuition

Pick a balloon k to burst last in the interval (i, j). This splits the problem into two subproblems: bursting balloons in (i, k) and (k, j). Try all possible candidates for the last balloon.

Thought Process

Pad the array with 1 at both ends.
Define a function solve(i, j) that returns max coins from interval [i, j].
Base case: If i > j, return 0.
Recursive step: max(solve(i, k-1) + solve(k+1, j) + A[i-1]*A[k]*A[j+1]) for all k in [i, j].

⏱ Exponential💾 O(N) for recursion

Detailed Dry Run

nums=[3, 1, 5] -> A=[1, 3, 1, 5, 1] solve(1, 3) where length is 3. Try k=2 as last: solve(1, 1) + solve(3, 3) + 111 = 3 + 25 + 1 = 29.

java

public class Main {
    public static int solve(int[] A, int i, int j) {
        if (i > j) return 0;
        int max = 0;
        for (int k = i; k <= j; k++) {
            int coins = A[i - 1] * A[k] * A[j + 1] + solve(A, i, k - 1) + solve(A, k + 1, j);
            max = Math.max(max, coins);
        }
        return max;
    }

    public static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] A = new int[n + 2];
        A[0] = 1; A[n + 1] = 1;
        for (int i = 0; i < n; i++) A[i + 1] = nums[i];
        return solve(A, 1, n);
    }

    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8})); // 167
    }
}

Approach 2

Level II: Memoization (Top-Down Interval DP)

Intuition

The brute force re-solves the same (i, j) intervals. We add a 2D memo table to cache the max coins for each interval.

Visual

nums=[3,1,5,8], A=[1,3,1,5,8,1]
memo[1][4] = max coins for range (1..4)
After first computation, reused whenever (1,4) is subproblem!

⏱ O(N^3)💾 O(N^2)

Detailed Dry Run

A=[1,3,1,5,8,1]. memo[1][4]: try k=1,2,3,4 as last balloon. k=3 gives 351+memo[1][2]+memo[4][4]=15+9+40=... Cached!

java

public class Main {
    static int[] A;
    static int[][] memo;
    public static int solve(int i, int j) {
        if (i > j) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int res = 0;
        for (int k = i; k <= j; k++) {
            int coins = A[i - 1] * A[k] * A[j + 1] + solve(i, k - 1) + solve(k + 1, j);
            res = Math.max(res, coins);
        }
        return memo[i][j] = res;
    }

    public static int maxCoins(int[] nums) {
        int n = nums.length;
        A = new int[n + 2];
        A[0] = A[n + 1] = 1;
        for (int i = 0; i < n; i++) A[i + 1] = nums[i];
        memo = new int[n + 2][n + 2];
        for (int[] row : memo) java.util.Arrays.fill(row, -1);
        return solve(1, n);
    }

    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8})); // 167
    }
}

⚠️ Common Pitfalls & Tips

This is an interval DP problem. The key insight — picking the LAST balloon to burst — allows clean decomposition. Memoization here gives the same O(N^3) as bottom-up but is easier to reason about.

Approach 3

Level III: Dynamic Programming (Interval/Matrix Chain)

Intuition

Instead of deciding which balloon to burst first, we decide which balloon k is burst last in the interval (i, j). This allows us to split the problem into two independent subproblems: bursting balloons in (i, k) and (k, j).

Thought Process

Pad the array with 1 at both ends.
dp[i][j] = max coins from bursting balloons between index i and j (exclusive).
For each length len from 1 to n:
- For each start i from 1 to n - len + 1:
  - End j = i + len - 1.
  - For k from i to j (last balloon to burst):
    - coins = nums[i-1] * nums[k] * nums[j+1] + dp[i][k-1] + dp[k+1][j].

⏱ O(N^3)💾 O(N^2)

Detailed Dry Run

nums = [3, 1, 5] Boundary padded: [1, 3, 1, 5, 1]

Interval	Last k	Calculation	Result
(1,1)	1	131 + 0 + 0	3
(2,2)	2	315 + 0 + 0	15
(3,3)	3	551 + 0 + 0	25
(1,2)	1	135 + 0 + dp[2][2] = 15+15	30
(1,2)	2	115 + dp[1][1] + 0 = 5+3	8

java

public class Main {
    public static int maxCoins(int[] nums) {
        int n = nums.length;
        int[] padded = new int[n + 2];
        padded[0] = 1; padded[n + 1] = 1;
        System.arraycopy(nums, 0, padded, 1, n);

        int[][] dp = new int[n + 2][n + 2];

        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                for (int k = i; k <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], 
                        padded[i - 1] * padded[k] * padded[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
                }
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        System.out.println(maxCoins(new int[]{3, 1, 5, 8})); // 167
    }
}

⚠️ Common Pitfalls & Tips

The intuition for O(N^3) interval DP is often hard to find. Remember: "last item to be processed" is a common pattern for problems involving shrinking ranges (like Matrix Chain Multiplication).

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Visual Representation

s = ")()())"

Substrings:
() -> 2
()() -> 4 (Max)

DP Strategy:
dp[i] = length of longest valid parentheses ending at index i.

Hard

Examples

Input: s = "(()"
Output: 2
The longest valid parentheses substring is "()".

Input: s = ")()())"
Output: 4
The longest valid parentheses substring is "()()".

Approach 1

Level I: Dynamic Programming

Intuition

We use a 1D DP array where dp[i] is the length of the longest valid parentheses ending at index i.

Thought Process

If s[i] == '(', dp[i] = 0 (valid substring can't end with open paren).
If s[i] == ')':
- If s[i-1] == '(', then dp[i] = dp[i-2] + 2.
- If s[i-1] == ')' and s[i - dp[i-1] - 1] == '(', then dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2.
Keep track of maximum dp[i].

⏱ O(N)💾 O(N)

Detailed Dry Run

s = "()()"

i	char	Calculation	dp[i]
0	(	-	0
1	)	dp[0-1]+2 = 2	2
2	(	-	0
3	)	dp[3-2]+2 = dp[1]+2 = 4	4

java

public class Main {
    public static int longestValidParentheses(String s) {
        int maxLen = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()())")); // 4
    }
}

Approach 2

Level II: Stack-Based Approach

Intuition

Use a stack to track unmatched parenthesis indices. Whenever we find a matching pair, the valid length is i - stack.peek().

Visual

s = ")()())"
stack: [-1]
i=0 ')': stack = []  -> push 0? No, stack is empty -> push i=0
i=1 '(': stack = [0, 1]
i=2 ')': pop 1 -> stack = [0], len = 2-0=2
i=3 '(': stack = [0, 3]
i=4 ')': pop 3 -> stack = [0], len = 4-0=4
i=5 ')': pop 0 -> stack = [], push 5
Max = 4

⏱ O(N)💾 O(N)

Detailed Dry Run

s="())". stack=[-1]. i=0 '(': push 0. i=1 ')': pop 0, len=1-(-1)=2, max=2. i=2 ')': pop -1, empty -> push 2. Result = 2.

java

import java.util.*;

public class Main {
    public static int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()()")); // 4
    }
}

⚠️ Common Pitfalls & Tips

Initialize the stack with -1 as a sentinel base index. Without this, first close parenthesis would fail to compute length (0 - nothing = invalid).

Approach 3

Level III: Two Counters (Optimal Space)

Intuition

We can optimize space to O(1) by scanning the string twice (left-to-right and right-to-left) while keeping track of left and right parentheses counts.

Logic Steps

Scan Left to Right:
- left++ for '(', right++ for ')'.
- If left == right, current length is 2 * left. Update max.
- If right > left, reset both to 0.
Scan Right to Left:
- Repeat same logic but reset if left > right.

⏱ O(N)💾 O(1)

Detailed Dry Run

s = "(()"

L-R: '('(L1,R0), '('(L2,R0), ')'(L2,R1). L!=R. Max=0.
R-L: ')'(L0,R1), '('(L1,R1) -> Max=2, '('(L2,R1) -> Reset. Result: 2.

java

public class Main {
    public static int longestValidParentheses(String s) {
        int left = 0, right = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') left++; else right++;
            if (left == right) maxLen = Math.max(maxLen, 2 * right);
            else if (right > left) { left = 0; right = 0; }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') left++; else right++;
            if (left == right) maxLen = Math.max(maxLen, 2 * left);
            else if (left > right) { left = 0; right = 0; }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses("(()")); // 2
    }
}

Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

Visual Representation

word1 = "horse", word2 = "ros"

Steps:
1. horse -> rorse (replace 'h' with 'r')
2. rorse -> rose (remove 'r')
3. rose  -> ros  (remove 'e')
Result: 3

DP Strategy:
dp[i][j] = min distance between word1[0...i] and word2[0...j]

Hard

Examples

Input: word1 = "horse", word2 = "ros"
Output: 3
horse -> rorse (replace 'h' with 'r') -> rose (remove 'r') -> ros (remove 'e')

Input: word1 = "intention", word2 = "execution"
Output: 5

Approach 1

Level I: Dynamic Programming (2D)

Intuition

We build a 2D table where dp[i][j] is the minimum operations to convert word1[0...i] to word2[0...j].

Thought Process

If word1[i-1] == word2[j-1], no operation is needed for the current character: dp[i][j] = dp[i-1][j-1].
If they are different, we take the minimum of three operations:
- Insert: 1 + dp[i][j-1]
- Delete: 1 + dp[i-1][j]
- Replace: 1 + dp[i-1][j-1]
Base cases: Converting string to empty string requires i (or j) deletions.

⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

word1 = "abc", word2 = "abd"

i\j	""	'a'	'b'	'd'
""	0	1	2	3
'a'	1	0 (match)	1	2
'b'	2	1	0 (match)	1
'c'	3	2	1	1 (replace 'c' with 'd')

java

public class Main {
    public static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // 3
    }
}

Approach 2

Level II: Memoization (Top-Down 2D)

Intuition

The recursive brute force for edit distance has overlapping subproblems (i, j). Cache results to avoid recomputation.

Visual

word1='horse', word2='ros'
solve(0,0): 'h'!='r' -> min(solve(1,1), solve(1,0), solve(0,1))
solve(1,1): cached after first call!

⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

word1="ab", word2="a". solve(0,0): 'a'=='a' -> solve(1,1). solve(1,1): 'b'!='', return 1+solve(2,1)=1.

java

import java.util.Arrays;

public class Main {
    static int[][] memo;
    public static int solve(String w1, String w2, int i, int j) {
        if (i == w1.length()) return w2.length() - j;
        if (j == w2.length()) return w1.length() - i;
        if (memo[i][j] != -1) return memo[i][j];
        if (w1.charAt(i) == w2.charAt(j)) return memo[i][j] = solve(w1, w2, i+1, j+1);
        return memo[i][j] = 1 + Math.min(solve(w1, w2, i+1, j+1),
            Math.min(solve(w1, w2, i+1, j), solve(w1, w2, i, j+1)));
    }

    public static int minDistance(String word1, String word2) {
        memo = new int[word1.length()][word2.length()];
        for (int[] r : memo) Arrays.fill(r, -1);
        return solve(word1, word2, 0, 0);
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // 3
    }
}

Approach 3

Level III: Space Optimized (1D)

Intuition

To compute dp[i][j], we only need the current row and the previous row. Specifically, dp[i-1][j-1] (diagonal), dp[i-1][j] (up), and dp[i][j-1] (left).

Logic Steps

Initialize curr array of size n+1 with base case values 0...n.
Iterate through word1. For each i:
- Cache dp[i-1][j-1] in a prev variable.
- Update the curr[0] for the base case (conversions from word1[0...i] to empty string).
- Inner loop through word2 to update curr[j].
Return curr[n].

⏱ O(N * M)💾 O(Min(N, M))

Detailed Dry Run

word1 = "abc", word2 = "abd" Focus on space reduction where we store only 1 row. Diag (prev) cache is critical to keep the value from the 'upper-left' cell before it was overwritten.

java

public class Main {
    public static int minDistance(String word1, String word2) {
        int n = word2.length();
        int[] dp = new int[n + 1];
        for (int j = 0; j <= n; j++) dp[j] = j;

        for (int i = 1; i <= word1.length(); i++) {
            int prev = dp[0];
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prev;
                } else {
                    dp[j] = 1 + Math.min(prev, Math.min(dp[j], dp[j - 1]));
                }
                prev = temp;
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("abc", "abd")); // 1
    }
}

Frog Jump

A frog is crossing a river. The river is divided into units and at each unit there may or may not be a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Visual Representation

Stones: [0, 1, 3, 5, 6, 8, 12, 17]

Jump 1: 0 -> 1 (Size 1)
Jump 2: 1 -> 3 (Size 2, allowed: 1-1, 1, 1+1)
Jump 3: 3 -> 5 (Size 2, allowed: 1, 2, 3)
...

Hard

Examples

Input: stones = [0, 1, 3, 5, 6, 8, 12, 17]
Output: true
0->1(1)->3(2)->5(2)->8(3)->12(4)->17(5)

Input: stones = [0, 1, 2, 3, 4, 8, 9, 11]
Output: false

Approach 1

Level I: Brute Force (Recursion)

Intuition

Try every valid jump from the current stone. For a stone at index i reached with a jump of k, the next jump can be k-1, k, or k+1.

Thought Process

Start at the first stone.
From stone at position pos, if we reached it with jump k, try positions pos + k - 1, pos + k, and pos + k + 1.
Base case: If we reach the last stone, return true.
If the target position has a stone, recurse.

⏱ O(3^N)💾 O(N)

Detailed Dry Run

stones = [0, 1, 3]

Start at 0. Only way to start is jump 1 to stone 1.
At 1, last jump was 1. Next jumps: 0 (skip), 1, 2.
Try k=2: 1 + 2 = 3. Stone 3 exists! Reached target.

java

import java.util.*;

public class Main {
    public static boolean solve(int pos, int k, Set<Integer> stoneSet, int target) {
        if (pos == target) return true;
        if (pos > target || k <= 0) return false;

        for (int nextK = k - 1; nextK <= k + 1; nextK++) {
            if (nextK > 0 && stoneSet.contains(pos + nextK)) {
                if (solve(pos + nextK, nextK, stoneSet, target)) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] stones = {0, 1, 3, 5, 6, 8, 12, 17};
        Set<Integer> stoneSet = new HashSet<>();
        for (int stone : stones) stoneSet.add(stone);
        System.out.println(solve(1, 1, stoneSet, 17)); // false
    }
}

Approach 2

Level II: Memoization (Top-Down)

Intuition

Cache (position, lastJump) states to avoid recomputing the same frog position visited with the same jump size.

Visual

stones=[0,1,3,5,6], target=6
solve(1, 1): -> solve(3, 2) or solve(3, 1)
solve(3,2): cached after first call!

⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

Cache key=(pos, k). solve(1,1) -> solve(3,2). solve(3,2) -> solve(5,2) or solve(5,3). Cached when revisited.

java

import java.util.*;

public class Main {
    public static boolean canCross(int[] stones) {
        Set<Integer> stoneSet = new HashSet<>();
        for (int s : stones) stoneSet.add(s);
        Map<String, Boolean> memo = new HashMap<>();
        return solve(stoneSet, stones[stones.length-1], 1, 1, memo);
    }

    static boolean solve(Set<Integer> stoneSet, int target, int pos, int k, Map<String,Boolean> memo) {
        if (pos == target) return true;
        String key = pos + "," + k;
        if (memo.containsKey(key)) return memo.get(key);
        boolean res = false;
        for (int step = k-1; step <= k+1 && !res; step++) {
            if (step > 0 && stoneSet.contains(pos + step))
                res = solve(stoneSet, target, pos+step, step, memo);
        }
        memo.put(key, res);
        return res;
    }

    public static void main(String[] args) {
        System.out.println(canCross(new int[]{0,1,3,5,6,8,12,17})); // true
    }
}

Approach 3

Level III: Dynamic Programming (Map of Sets)

Intuition

We maintain a map where the key is the stone's position and the value is a set of all possible jump sizes that could have landed the frog on that stone.

Thought Process

Initialize Map<Integer, Set<Integer>>. For each stone, create an empty set.
Add jump size 0 to the first stone (base case).
For each stone s:
- For each jump size k in map.get(s):
  - For each next jump step in {k-1, k, k+1}:
    - If step > 0 and map.containsKey(s + step):
      - Add step to the set for stone s + step.
If the set for the last stone is not empty, return true.

⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

stones = [0, 1, 3]

Stone	Jump Sizes
0	{1} (Initial jump is 1)
1	{1} (from 0+1)
3	{2} (from 1+2, k=1 -> k+1=2)
Result: True (Set for 3 is not empty)

java

import java.util.*;

public class Main {
    public static boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int stone : stones) map.put(stone, new HashSet<>());
        map.get(0).add(0);

        for (int stone : stones) {
            for (int k : map.get(stone)) {
                for (int step = k - 1; step <= k + 1; step++) {
                    if (step > 0 && map.containsKey(stone + step)) {
                        map.get(stone + step).add(step);
                    }
                }
            }
        }
        return !map.get(stones[stones.length - 1]).isEmpty();
    }

    public static void main(String[] args) {
        int[] stones = {0, 1, 3, 5, 6, 8, 12, 17};
        System.out.println(canCross(stones)); // true
    }
}

Minimum Path Sum in Grid

Given a m x n grid filled with non-negative numbers, find a path from top-left to bottom-right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Visual Representation

Grid:
[1, 3, 1]
[1, 5, 1]
[4, 2, 1]

Paths:
1-3-1-1-1 = 7 (Min)
1-1-5-2-1 = 10
1-1-4-2-1 = 9

Medium

Examples

Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Input: grid = [[1, 2, 3], [4, 5, 6]]
Output: 12

Approach 1

Level I: Dynamic Programming (2D)

Intuition

The minimum sum to reach cell (i, j) is the value of the current cell plus the minimum of the paths reaching from above (i-1, j) or from the left (i, j-1).

Thought Process

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
Edges: For the first row, you can only come from the left. For the first column, you can only come from above.
Base Case: dp[0][0] = grid[0][0].

⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

grid = [[1, 3], [1, 5]]

Cell	Calculation	Sum
(0, 0)	Base	1
(0, 1)	1 + grid[0][1] = 1+3	4
(1, 0)	1 + grid[1][0] = 1+1	2
(1, 1)	5 + min(dp[0][1], dp[1][0]) = 5 + min(4, 2)	7

java

public class Main {
    public static int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                int fromUp = (i > 0) ? dp[i-1][j] : Integer.MAX_VALUE;
                int fromLeft = (j > 0) ? dp[i][j-1] : Integer.MAX_VALUE;
                dp[i][j] = grid[i][j] + Math.min(fromUp, fromLeft);
            }
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(minPathSum(grid)); // 7
    }
}

Approach 2

Level II: Memoization (Top-Down Recursion)

Intuition

The recursive brute force for grid path counting has overlapping subproblems. We cache each (i, j) state so we never recompute it.

Visual

Memo Grid (m=3, n=3):
| 0 | 1 | 1 |
| 1 | 2 | ? |  <- memo[1][2] reused by (2,2)
| 1 | ? | ? |

⏱ O(M * N)💾 O(M * N) for memo + O(M + N) recursion stack

Detailed Dry Run

m=3, n=3. memo[2][2] = memo[1][2] + memo[2][1]. Both sub-calls are cached after first computation.

java

public class Main {
    static int[][] memo;
    public static int solve(int m, int n) {
        if (m == 1 || n == 1) return 1;
        if (memo[m][n] != 0) return memo[m][n];
        return memo[m][n] = solve(m - 1, n) + solve(m, n - 1);
    }

    public static int uniquePaths(int m, int n) {
        memo = new int[m + 1][n + 1];
        return solve(m, n);
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7)); // 28
    }
}

⚠️ Common Pitfalls & Tips

Recursion adds O(M+N) stack overhead compared to the iterative DP. For very large grids, prefer the iterative approach to avoid stack overflow.

Approach 3

Level III: Space Optimized (1D)

Intuition

To compute dp[i][j], we only need the value above it (previous row) and the value to its left (current row). We can use a single array of size n.

Logic Steps

Initialize row array of size n with Infinity.
Set row[0] = 0 (starting point for accumulation).
For each i (row):
- row[0] += grid[i][0]
- For each j (col from 1 to n-1):
  - row[j] = grid[i][j] + min(row[j], row[j-1]).
Return row[n-1].

⏱ O(M * N)💾 O(N)

Detailed Dry Run

grid = [[1, 3], [1, 5]]

Row	row array calculation	State
0	[1, 1+3=4]	[1, 4]
1	[1+1=2, 5+min(2, 4)=7]	[2, 7]

java

public class Main {
    public static int minPathSum(int[][] grid) {
        int n = grid[0].length;
        int[] row = new int[n];
        row[0] = grid[0][0];
        for (int j = 1; j < n; j++) row[j] = row[j - 1] + grid[0][j];

        for (int i = 1; i < grid.length; i++) {
            row[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                row[j] = grid[i][j] + Math.min(row[j], row[j - 1]);
            }
        }
        return row[n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 2}, {1, 1}};
        System.out.println(minPathSum(grid)); // 3
    }
}

Maximal Square

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Visual Representation

Matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

The 2x2 square of 1s at (1,2) to (2,3) is one of the squares.
Wait, there is a larger one? No, area is 4.

DP Strategy:
dp[i][j] = side length of the largest square ending at (i, j).

Medium

Examples

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Approach 1

Level I: Dynamic Programming (2D)

Intuition

A square of size k ending at (i, j) can only be formed if there are squares of size k-1 ending at (i-1, j), (i, j-1), and (i-1, j-1).

Thought Process

dp[i][j] represents the side length of the largest square ending at matrix[i][j].
If matrix[i][j] == '1':
- dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
Keep track of the maximum side length found so far.
Result = maxSide * maxSide.

⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

Matrix: 1 1 1 1

i\j	0	1
0	1	1
1	1	min(1, 1, 1)+1 = 2
Result: 2^2 = 4

java

public class Main {
    public static int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxSide = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        char[][] matrix = {{'1','0','1'}, {'1','1','1'}, {'1','1','1'}};
        System.out.println(maximalSquare(matrix)); // 4
    }
}

Approach 2

Level II: Memoization (Top-Down)

Intuition

Cache the result of dp(i, j) so each cell is computed only once. The recurrence: dp(i,j) = min(dp(i-1,j), dp(i,j-1), dp(i-1,j-1)) + 1 if matrix[i][j]=='1'.

Visual

Matrix:        Memo:
1 1          1  1  1
1 1    ->    1  2  ?
1 1          1  ?  3  <- dp(2,2) = min(2,2,2)+1=3

⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

dp(2,2): matrix[2][2]='1'. min(dp(1,2)=2, dp(2,1)=2, dp(1,1)=2)+1=3. Area=9.

java

import java.util.Arrays;

public class Main {
    static int[][] memo;
    static char[][] mat;
    static int solve(int i, int j) {
        if (i < 0 || j < 0 || mat[i][j] == '0') return 0;
        if (memo[i][j] != -1) return memo[i][j];
        return memo[i][j] = 1 + Math.min(solve(i-1,j), Math.min(solve(i,j-1), solve(i-1,j-1)));
    }

    public static int maximalSquare(char[][] matrix) {
        mat = matrix; int m = matrix.length, n = matrix[0].length;
        memo = new int[m][n];
        for (int[] r : memo) Arrays.fill(r, -1);
        int maxS = 0;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) maxS = Math.max(maxS, solve(i,j));
        return maxS * maxS;
    }

    public static void main(String[] args) {
        char[][] m = {{"1","1"},{"1","1"}};
        System.out.println(maximalSquare(m)); // 4
    }
}

Approach 3

Level III: Space Optimized (1D)

Intuition

We only need the previous row and the current row. Specifically, dp[i-1][j], dp[i][j-1], and the diagonal dp[i-1][j-1].

Logic Steps

Initialize a dp array of size n + 1.
Use a prev variable to store the diagonal value dp[i-1][j-1] from the previous row.
Iterate row by row.

⏱ O(M * N)💾 O(N)

Detailed Dry Run

Same logic as 2D but overwriting the same row array. 'prev' variable caches the upper-left (diagonal) value before it gets updated for the current row's calculation.

java

public class Main {
    public static int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[] dp = new int[cols + 1];
        int maxSide = 0, prev = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j - 1], dp[j]), prev) + 1;
                    maxSide = Math.max(maxSide, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        char[][] matrix = {{'1','1'}, {'1','1'}};
        System.out.println(maximalSquare(matrix)); // 4
    }
}

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Visual Representation

s = "aab"

Valid partitions:
["a", "a", "b"] -> 2 cuts
["aa", "b"]     -> 1 cut (Min)
Result: 1

Hard

Examples

Input: s = "aab"
Output: 1
The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Input: s = "a"
Output: 0

Approach 1

Level I: Brute Force (Recursion)

Intuition

Try every possible split point for the string. If the prefix is a palindrome, recursively find the minimum cuts for the remaining suffix.

Thought Process

solve(i) returns min cuts for s[i...n-1].
Base case: If s[i...n-1] is a palindrome, return 0 (no more cuts needed).
For each j from i to n-1:
- If s[i...j] is a palindrome:
  - res = min(res, 1 + solve(j + 1)).

⏱ O(2^N)💾 O(N)

Detailed Dry Run

s = "aab"

"a" is pal. solve("ab")
"aa" is pal. solve("b") -> "b" is pal, returns 0. Total 1+0=1. Result: 1

java

public class Main {
    private static boolean isPal(String s, int i, int j) {
        while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
        return true;
    }

    public static int solve(String s, int i) {
        if (i == s.length() || isPal(s, i, s.length() - 1)) return 0;
        int min = s.length();
        for (int j = i; j < s.length(); j++) {
            if (isPal(s, i, j)) {
                min = Math.min(min, 1 + solve(s, j + 1));
            }
        }
        return min;
    }

    public static void main(String[] args) {
        System.out.println(solve("aab", 0)); // 1
    }
}

Approach 2

Level II: Memoization (Top-Down DP)

Intuition

Cache the result of solve(i) (min cuts for suffix s[i:]) using a memo array. Also precompute palindrome check to avoid O(N) palindrome check every time.

Visual

s = "aab"
memo[2] = 0 ("b" is palindrome)
memo[1] = 1 ("ab" -> "a"|"b" = 1 cut, or "ab" not pal)
memo[0] = 1 ("aa"|"b" = 1 cut, memo[2] cached!)

⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

s="aab". solve(2)=0. solve(1)=1+solve(2)=1. solve(0): is_pal[0][1]=True -> 1+solve(2)=1. Result=1.

java

import java.util.Arrays;

public class Main {
    public static int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for (int j = 0; j < n; j++)
            for (int i = 0; i <= j; i++)
                if (s.charAt(i)==s.charAt(j) && (j-i<=2 || isPal[i+1][j-1]))
                    isPal[i][j] = true;

        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        return solve(s, isPal, memo, 0);
    }

    static int solve(String s, boolean[][] isPal, int[] memo, int i) {
        if (i == s.length() || isPal[i][s.length()-1]) return 0;
        if (memo[i] != -1) return memo[i];
        int min = s.length();
        for (int j = i; j < s.length(); j++)
            if (isPal[i][j]) min = Math.min(min, 1 + solve(s, isPal, memo, j+1));
        return memo[i] = min;
    }

    public static void main(String[] args) {
        System.out.println(minCut("aab")); // 1
    }
}

Approach 3

Level III: Dynamic Programming (Two Passes)

Intuition

We need two DP arrays. One 2D array isPal[i][j] to precompute if s[i...j] is a palindrome. Another 1D array cuts[i] to store the minimum cuts needed for s[0...i].

Thought Process

Precompute isPal[i][j] using standard palindrome DP: s[i] == s[j] && (j-i < 2 || isPal[i+1][j-1]).
Initialize cuts[i] = i (max possible cuts: each char separate).
For j from 0 to n-1:
- If isPal[0][j] is true, cuts[j] = 0 (no cuts needed for entire prefix).
- Else, for i from 1 to j:
  - If isPal[i][j] is true, cuts[j] = min(cuts[j], cuts[i-1] + 1).

⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

s = "aab" Precomputed isPal: [0,0]=T, [1,1]=T, [2,2]=T, [0,1]=T ("aa")

j	isPal(0,j)	Action	cuts[j]
0	T	0 cuts	0
1	T	0 cuts	0
2	F	cuts[1]+1 ("aa"	"b")
Result: 1

java

public class Main {
    public static int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || isPal[i + 1][j - 1])) {
                    isPal[i][j] = true;
                }
            }
        }

        int[] cuts = new int[n];
        for (int j = 0; j < n; j++) {
            if (isPal[0][j]) {
                cuts[j] = 0;
            } else {
                cuts[j] = j;
                for (int i = 1; i <= j; i++) {
                    if (isPal[i][j]) cuts[j] = Math.min(cuts[j], cuts[i - 1] + 1);
                }
            }
        }
        return cuts[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(minCut("aab")); // 1
    }
}

Interleaving String

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Visual Representation

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Characters from s1 (bold), s2 (italic):
a a d b b c b c a c
(a)(a)(d)(b)(b)(c)(b)(c)(a)(c)
s1 s1 s2 s2 s2 s1 s2 s1 s2 s1

Result: True

Medium

Examples

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Approach 1

Level I: Dynamic Programming (Bottom-Up 2D)

Intuition

We use a 2D table dp[i][j] to represent if s3[0...i+j-1] is formed by interleaving s1[0...i-1] and s2[0...j-1].

Thought Process

dp[i][j] is true if:
- dp[i-1][j] is true AND s1[i-1] == s3[i+j-1]
- OR dp[i][j-1] is true AND s2[j-1] == s3[i+j-1]
Base case: dp[0][0] = true.
Base case: dp[i][0] matches only against s1. dp[0][j] matches only against s2.

⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

s1="a", s2="b", s3="ab"

i\j	""	'b'
""	T	F (s2[0]!=s3[0])
'a'	T (s1[0]==s3[0])	T (s1[0]==s3[0] or s2[0]==s3[1])
Result: True

java

public class Main {
    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;

        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i > 0) dp[i][j] |= (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
                if (j > 0) dp[i][j] |= (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return dp[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("aab", "db", "aadbb")); // true
    }
}

Approach 2

Level II: Memoization (Top-Down 2D)

Intuition

The 2D DP bottom-up approach fills the entire table. Top-down memoization only explores reachable states. Both have the same asymptotic complexity.

Visual

s1="a", s2="b", s3="ab"
solve(0,0): s1[0]='a'==s3[0] -> solve(1,0)
  or s2[0]='b'!=s3[0] -> blocked
solve(1,0): s2[0]='b'==s3[1] -> solve(1,1)=True

⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

s1="a", s2="b", s3="ab". solve(0,0): 'a'=='a' -> solve(1,0). solve(1,0): 'b'=='b' -> solve(1,1)=True.

java

import java.util.*;

public class Main {
    static Boolean[][] memo;
    public static boolean solve(String s1, String s2, String s3, int i, int j) {
        if (i==s1.length() && j==s2.length()) return true;
        if (i+j >= s3.length()) return false;
        if (memo[i][j] != null) return memo[i][j];
        boolean res = false;
        if (i<s1.length() && s1.charAt(i)==s3.charAt(i+j)) res = solve(s1,s2,s3,i+1,j);
        if (!res && j<s2.length() && s2.charAt(j)==s3.charAt(i+j)) res = solve(s1,s2,s3,i,j+1);
        return memo[i][j] = res;
    }

    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length()+s2.length()!=s3.length()) return false;
        memo = new Boolean[s1.length()+1][s2.length()+1];
        return solve(s1,s2,s3,0,0);
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("aab","db","aadbb")); // true
    }
}

Approach 3

Level III: Space Optimized (1D)

Intuition

Like most 2D matrix DP problems where dp[i][j] only depends on dp[i-1][j] and dp[i][j-1], we can reduce space to O(M) (where M is length of s2).

Logic Steps

Initialize a dp array of size s2.length + 1.
In the outer loop (s1), dp[j] will represent dp[i][j].
dp[j] is updated as (dp[j] && s1[i-1] == s3[i+j-1]) || (dp[j-1] && s2[i-1] == s3[i+j-1]).

⏱ O(N * M)💾 O(M)

Detailed Dry Run

Same logic, but we only keep one row. The 'up' dependency comes from the array value before modification, and 'left' dependency comes from the array value after modification (current row).

java

public class Main {
    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        boolean[] dp = new boolean[s2.length() + 1];
        dp[0] = true;
        for (int j = 1; j <= s2.length(); j++) {
            dp[j] = dp[j-1] && s2.charAt(j-1) == s3.charAt(j-1);
        }

        for (int i = 1; i <= s1.length(); i++) {
            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = 1; j <= s2.length(); j++) {
                dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || 
                        (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return dp[s2.length()];
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("a", "b", "ab")); // true
    }
}

Minimum Cost to Merge Stones

There are n piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles.

Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Visual Representation

stones = [3, 2, 4, 1], k = 2

[3, 2, 4, 1] -> [5, 4, 1] (cost 5)
[5, 4, 1] -> [5, 5] (cost 5)
[5, 5] -> [10] (cost 10)
Total Cost: 20 (Min)

Hard

Examples

Input: stones = [3, 2, 4, 1], k = 2
Output: 20

Input: stones = [3, 2, 4, 1], k = 3
Output: -1
After merging 3 piles, we have 2 piles left. We need exactly k=3 piles to merge.

Approach 1

Level I: Brute Force (Recursion)

Intuition

Try all possible splitting points in the current range [i, j] to merge into m piles. This is a classic exhaustive search for partition problems.

Thought Process

solve(i, j, piles) returns min cost to merge stones[i...j] into piles piles.
Transitions:
- To get piles piles from [i, j], we can split into [i, k] (merged into 1 pile) and [k+1, j] (merged into piles-1 piles).
- solve(i, j, piles) = min(solve(i, k, 1) + solve(k + 1, j, piles - 1)).
Base case: solve(i, i, 1) = 0.

⏱ Exponential💾 O(N)

Detailed Dry Run

stones = [3, 2, 4], K = 3

solve(0, 2, 1) = solve(0, 2, 3) + sum(3, 2, 4).
solve(0, 2, 3) = split into [0,0] (1 pile) and [1,2] (2 piles).
Result: 9.

java

public class Main {
    public static int solve(int[] stones, int K, int i, int j, int m) {
        if (i == j) return m == 1 ? 0 : 1000000;
        if (m == 1) return solve(stones, K, i, j, K) + sum(stones, i, j);

        int res = 1000000;
        for (int k = i; k < j; k += K - 1) {
            res = Math.min(res, solve(stones, K, i, k, 1) + solve(stones, K, k + 1, j, m - 1));
        }
        return res;
    }
    private static int sum(int[] s, int i, int j) { 
        int sum = 0; for(int k=i; k<=j; k++) sum += s[k]; return sum; 
    }

    public static void main(String[] args) {
        System.out.println(solve(new int[]{3, 2, 4, 1}, 2, 0, 3, 1)); // 20
    }
}

Approach 2

Level II: Memoization (Top-Down 3D)

Intuition

Cache the result of solve(i, j, m) — the minimum cost to merge stones[i..j] into m piles. This avoids recomputing the same interval+pile-count combinations.

Visual

solve(0,3,1) [merge ALL into 1 pile]
  -> solve(0,1,1) + solve(2,3,1) [split and merge]
  Both sub-calls cached after first computation!

⏱ O(N^3 / K)💾 O(N^2 * K)

Detailed Dry Run

stones=[3,2,4], K=3. solve(0,2,1): need K=3 piles first. solve(0,2,3)=0 (3 stones, 3 piles is base). Cost=9. Cached.

java

import java.util.Arrays;

public class Main {
    public static int mergeStones(int[] stones, int K) {
        int n = stones.length;
        if ((n-1)%(K-1)!=0) return -1;
        int[] pre = new int[n+1];
        for (int i=0;i<n;i++) pre[i+1]=pre[i]+stones[i];
        int[][][] memo = new int[n][n][K+1];
        for (int[][] a : memo) for (int[] b : a) Arrays.fill(b,-1);
        return solve(stones,K,pre,memo,0,n-1,1);
    }

    static int solve(int[] s,int K,int[] pre,int[][][] memo,int i,int j,int m) {
        if (i==j) return m==1?0:1000000;
        if (memo[i][j][m]!=-1) return memo[i][j][m];
        if (m==1) {
            int cost=solve(s,K,pre,memo,i,j,K)+(pre[j+1]-pre[i]);
            return memo[i][j][1]=cost;
        }
        int res=1000000;
        for (int k=i;k<j;k+=K-1)
            res=Math.min(res,solve(s,K,pre,memo,i,k,1)+solve(s,K,pre,memo,k+1,j,m-1));
        return memo[i][j][m]=res;
    }

    public static void main(String[] args) {
        System.out.println(mergeStones(new int[]{3,2,4,1},2)); // 20
    }
}

Approach 3

Level III: Dynamic Programming (Interval/3D)

Intuition

This is a complex interval DP problem. We want to find the min cost to merge stones in range [i, j] into p piles.

Thought Process

dp[i][j][m] means the min cost to merge stones in stones[i...j] into m piles.
Transitions:
- To merge [i, j] into m piles, we can split it into [i, k] (merged into 1 pile) and [k+1, j] (merged into m-1 piles).
- dp[i][j][m] = min(dp[i][k][1] + dp[k+1][j][m-1]) for k in [i, j-1].
- Base Case: dp[i][i][1] = 0 (single pile is already 1 pile).
When m == 1, the cost is dp[i][j][k] + sum(stones[i...j]).

⏱ O(N^3 * K)💾 O(N^2 * K)

Detailed Dry Run

This is a classical matrix chain multiplication style problem. The state dp[i][j][m] helps track number of piles remaining, which is crucial because we can only merge EXACTLY K piles at once.

java

public class Main {
    public static int mergeStones(int[] stones, int K) {
        int n = stones.length;
        if ((n - 1) % (K - 1) != 0) return -1;

        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) prefixSum[i + 1] = prefixSum[i] + stones[i];

        int[][] dp = new int[n][n];
        for (int len = K; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int m = i; m < j; m += K - 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
                if ((len - 1) % (K - 1) == 0) {
                    dp[i][j] += prefixSum[j + 1] - prefixSum[i];
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(mergeStones(new int[]{3, 2, 4, 1}, 2)); // 20
    }
}

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.