SvenStack

🧩 Problem Description

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.

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

💬 Examples

Example 1

1
2
3

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

Example 2

1
2

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

💡 Intuition

This is a classic dynamic programming problem on a grid.
At each cell (i, j), the minimum path sum equals the cell value plus the smaller of the top or left neighbor:

1

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

We can compute this iteratively using either a 2D or 1D DP array.

🔢 Java Code (2D DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public 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 = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
}

🔢 Java Code (1D DP Optimization)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        
        for (int j = 1; j < n; j++) dp[j] = dp[j - 1] + grid[0][j];
        
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
            }
        }
        return dp[n - 1];
    }
}

⏱ Complexity Analysis

• Time: O(m × n)
• Space: O(n) (after optimization)

✍️ Summary

• Classic DP grid problem.
• Choose minimum between top and left cells.
• Can be optimized to 1D array.

Related problems:

• lc-62 (Unique Paths)
• lc-63 (Unique Paths II)
• lc-120 (Triangle)

🧩 Problem Description

A robot is located at the top-left corner of an m x n grid (marked start in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked finish).

How many possible unique paths are there?

💬 Examples

Example 1

1
2

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

Example 2

1
2
3
4
5
6

Input: m = 3, n = 2
Output: 3
Explanation:  
Right -> Down -> Down  
Down -> Down -> Right  
Down -> Right -> Down

💡 Intuition

At each cell (i, j), the number of unique paths to reach it is the sum of paths from the top (i-1, j) and from the left (i, j-1). This gives a dynamic programming relation.

Alternatively, this problem has a combinatorial solution using binomial coefficients: choosing (m-1) downs from (m+n-2) total moves.

🔢 Java Code (Dynamic Programming)

1
2
3
4
5
6
7
8
9
10
11
12
13

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

🔢 Java Code (Combinatorics)

1
2
3
4
5
6
7
8
9

class Solution {
    public int uniquePaths(int m, int n) {
        long res = 1;
        for (int i = 1; i <= m - 1; i++) {
            res = res * (n - 1 + i) / i;
        }
        return (int) res;
    }
}

⏱ Complexity Analysis

• DP approach:

  • Time: O(m × n)
  • Space: O(m × n) (can be optimized to O(n))

• Combinatorics:

  • Time: O(m)
  • Space: O(1)

✍️ Summary

• Grid path counting reduces to a classic DP problem.
• Alternatively, solve with binomial coefficient.
• Use combinatorics for very large grids to avoid DP overhead.

Related problems: lc-63 (Unique Paths II), lc-64 (Minimum Path Sum).

🧩 Problem Description

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

💬 Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2

Input: s = ""
Output: 0

💡 Intuition

We want the longest substring that forms valid parentheses. Three common approaches:

1. Stack approach: Track indices of unmatched parentheses.
2. Dynamic Programming: Use dp[i] to store the length of longest valid substring ending at i.
3. Two-pass scanning: Left-to-right and right-to-left counters for balance.

🔢 Java Code (Stack Approach)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public 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;
    }
}

🔢 Java Code (DP Approach)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n];
        int maxLen = 0;
        for (int i = 1; i < n; 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] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
}

⏱ Complexity Analysis

• Stack approach:

  • Time: O(n)
  • Space: O(n)

• DP approach:

  • Time: O(n)
  • Space: O(n)

• Two-pass scanning:

  • Time: O(n)
  • Space: O(1)

✍️ Summary

• Multiple methods exist: stack, DP, or two-pass counting.
• Stack is intuitive and straightforward.
• DP gives structured state-based reasoning.
• Two-pass is space-optimized.

Related problems: lc-20 (Valid Parentheses), lc-22 (Generate Parentheses), lc-301 (Remove Invalid Parentheses).

🧩 Problem Description

Given a non-empty array nums containing only positive integers, determine if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Return true if such a partition exists, otherwise return false.

💬 Examples

Example 1

1
2
3

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

Example 2

1
2
3

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

💡 Intuition

If the total sum is odd, it’s impossible to split into two equal subsets. Otherwise, the problem reduces to: can we find a subset with sum equal to target = totalSum / 2?

This is the classic subset sum problem and can be solved using dynamic programming (0/1 knapsack style) or using a bitset optimization. We aim for a boolean DP where dp[s] indicates whether a subset with sum s is achievable.

🔢 Java Code (1D DP - optimized 0/1 knapsack)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if ((sum & 1) == 1) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int s = target; s >= num; s--) {
                dp[s] = dp[s] || dp[s - num];
            }
            if (dp[target]) return true; // early exit
        }
        return dp[target];
    }
}

Alternative: Bitset (very fast in practice)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.*;

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if ((sum & 1) == 1) return false;
        int target = sum / 2;
        BitSet bits = new BitSet(target + 1);
        bits.set(0);
        for (int n : nums) {
            BitSet shifted = bits.get(0, target + 1 - n);
            // Implement left-shift by iterating backwards and setting bits appropriately.
            for (int i = target - n; i >= 0; i--) {
                if (bits.get(i)) bits.set(i + n);
            }
            if (bits.get(target)) return true;
        }
        return bits.get(target);
    }
}

Note: Java’s BitSet doesn’t provide a direct shiftLeft method — you can implement shifting by iterating or using a long-based trick for fixed-size bitsets. The 1D boolean DP is simpler and sufficiently fast for typical constraints.

⏱ Complexity Analysis

• Time: O(n × target) — where n is the number of elements.
• Space: O(target) — 1D DP array.

✍️ Summary

• Check total sum parity first.
• Reduce to subset-sum with target = totalSum / 2.
• Use 1D DP (iterate backwards) to avoid reusing elements.
• Early exit if dp[target] becomes true during iteration.

Related problems: lc-494 (Target Sum), lc-216 (Combination Sum III), lc-698 (Partition to K Equal Sum Subsets).

🧩 Problem Description

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product, and return the product.

💬 Examples

Example 1

1
2
3

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2

1
2
3

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2 because [-2,-1] is not a contiguous subarray in this case.

💡 Intuition

Because the product of numbers is affected by the sign, a negative number can turn a small (negative) product into a large positive one, and vice versa. Therefore, at each position we need to track both the maximum and minimum product ending at that position.

Let maxF[i] be the maximum product ending at i, and minF[i] the minimum product ending at i. Then:

1
2

maxF[i] = max(nums[i], nums[i] * maxF[i-1], nums[i] * minF[i-1])
minF[i] = min(nums[i], nums[i] * maxF[i-1], nums[i] * minF[i-1])

We can optimize space by keeping only previous max and min values.

🔢 Java Code (DP, O(1) space)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxProd = nums[0];
        int minProd = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; i++) {
            int x = nums[i];
            if (x < 0) { // swap when negative
                int tmp = maxProd;
                maxProd = minProd;
                minProd = tmp;
            }
            maxProd = Math.max(x, maxProd * x);
            minProd = Math.min(x, minProd * x);
            ans = Math.max(ans, maxProd);
        }
        return ans;
    }
}

⏱ Complexity Analysis

• Time: O(n) — single pass through the array.
• Space: O(1) — constant extra space.

✍️ Summary

• Track both maximum and minimum products at each step because negative numbers can flip signs.
• Swap max/min when encountering a negative number before updating.
• Keep a running global maximum answer.

Related problems

• lc-53 — Maximum Subarray (Kadane’s algorithm)
• lc-918 — Maximum Sum Circular Subarray

🧩 Problem Description

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.

💬 Examples

Example 1

1
2
3

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

Example 2

1
2

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

Example 3

1
2

Input: nums = [7,7,7,7,7,7,7]
Output: 1

💡 Approaches

1) Dynamic Programming (O(n²))

Let dp[i] be the length of the longest increasing subsequence ending at index i.
Transition: for each j < i, if nums[j] < nums[i] then dp[i] = max(dp[i], dp[j] + 1).
Answer is max(dp[i]) over all i.

2) Patience Sorting / Greedy + Binary Search (O(n log n))

Maintain an array tails[len] where tails[k] is the smallest possible tail value of an increasing subsequence with length k+1.
For each number x in nums, binary search the first index in tails with value ≥ x and replace it with x. If x is greater than all tails, append it. The length of tails is the LIS length.

This method gives O(n log n) time and O(n) space and is the recommended optimal solution for large inputs.

🔢 Java Code — DP (O(n²))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

🔢 Java Code — Patience Sorting (O(n log n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import java.util.*;

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        List<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();
    }
}

Note: Collections.binarySearch returns -(insertionPoint) - 1 when the key is not found; the code above converts it into the insertion point.

⏱ Complexity Analysis

• DP: Time O(n²), Space O(n).
• Patience Sorting: Time O(n log n), Space O(n).

✍️ Summary

• Use DP for clarity or small n.
• For large inputs, use the O(n log n) approach with tails + binary search (often called patience sorting).
• The tails array stores the smallest possible tail for an increasing subsequence of each length; its size equals the LIS length.

🧩 Problem Description

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.

You may assume the dictionary does not contain duplicate words.

💬 Examples

Example 1

1
2
3

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" -> "leet" + "code"

Example 2

1
2
3

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "applepenapple" -> "apple" + "pen" + "apple"

Example 3

1
2

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

💡 Intuition

We want to determine whether s can be split into valid words from wordDict. Two common approaches:

1. Dynamic Programming (DP): Let dp[i] be true if s[0..i) can be segmented. For each i, check all possible previous cuts j < i and if dp[j] is true and s[j..i) is in wordDict, set dp[i] = true.

2. BFS / Trie: Treat positions as nodes and edges when substring is a word; run BFS from position 0 to n to avoid redundant work.

DP is simple and efficient when implemented with a hash set for dictionary lookups and pruning via max word length.

🔢 Java Code (DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        int maxLen = 0;
        for (String w : wordDict) maxLen = Math.max(maxLen, w.length());
        
        for (int i = 1; i <= n; i++) {
            for (int l = 1; l <= maxLen && l <= i; l++) {
                if (!dp[i - l]) continue;
                if (dict.contains(s.substring(i - l, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

⏱ Complexity Analysis

• Time: O(n * L) where n = length of s, L = max word length; substring/hash lookups average O(1).
• Space: O(n) for DP array + O(m) for dictionary storage.

✍️ Summary

• DP with dictionary lookup and max-word-length optimization is the standard solution.
• BFS is an alternative that often performs well with proper visited pruning.

Related problems: lc-140 (Word Break II), lc-472 (Concatenated Words).

🧩 Problem Description

You are given an integer array coins representing different denominations of coins 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 cannot be made up by any combination of the coins, return -1.

💬 Examples

Example 1

1
2
3

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

Example 2

1
2

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

Example 3

1
2

Input: coins = [1], amount = 0
Output: 0

💡 Intuition

This is a classic DP problem similar to the unbounded knapsack problem.
We want the minimum number of coins to reach a target amount.

• Define dp[i] = minimum coins needed for amount i.
• Transition:

1

dp[i] = min(dp[i], dp[i - coin] + 1) for each coin <= i

• Base: dp[0] = 0.

If no solution exists, dp[amount] remains infinity (-1).

🔢 Java Code (DP Bottom-Up)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;

class Solution {
    public 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 >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

⏱ Complexity Analysis

• Time: O(amount * n), where n = number of coins.
• Space: O(amount) for the DP array.

✍️ Summary

• Classic coin change problem → DP solution.
• Transition: dp[i] = min(dp[i - coin] + 1).
• If no solution → return -1.

Related problems

• lc-518 — Coin Change II (count ways instead of minimum).
• lc-279 — Perfect Squares.

🧩 Problem Description

Given an integer n, return the least number of perfect square numbers (e.g., 1, 4, 9, 16, ...) which sum to n.

💬 Examples

Example 1

1
2
3

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4

Example 2

1
2
3

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9

💡 Intuition

This is a dynamic programming problem.

• Define dp[i] = minimum number of perfect squares to sum to i.
• Transition:

1

dp[i] = min(dp[i - j*j] + 1) for all j where j*j <= i

• Base case: dp[0] = 0.

Alternatively, this problem can also be solved with BFS (treating each remainder as a node).

🔢 Java Code (DP Approach)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

⏱ Complexity Analysis

• Time: O(n * sqrt(n)) — for each i, we check all squares up to sqrt(i).
• Space: O(n) — DP array.

✍️ Summary

• Classic DP problem.
• Transition: dp[i] = min(dp[i - j*j] + 1).
• Alternative BFS solution possible.

Related problems

• lc-139 — Word Break
• lc-322 — Coin Change

🧩 Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed.
The only constraint is: adjacent houses cannot be robbed 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.

💬 Examples

Example 1

1
2
3

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (1) + house 3 (3).

Example 2

1
2
3

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (2) + house 3 (9) + house 5 (1).

💡 Intuition

This is a dynamic programming problem.
At each house i, you decide to either:

• Rob it → value = nums[i] + dp[i-2]
• Skip it → value = dp[i-1]

Transition formula:

1

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

🔢 Java Code (DP Optimized)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int prev2 = nums[0];   // dp[i-2]
        int prev1 = Math.max(nums[0], nums[1]); // dp[i-1]
        
        for (int i = 2; i < nums.length; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

⏱ Complexity Analysis

• Time: O(n) — one pass through houses.
• Space: O(1) — only two variables stored.

✍️ Summary

• A classic DP problem.
• Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
• Space can be optimized to O(1).

Related problems

• lc-213 — House Robber II
• lc-337 — House Robber III