Unique Paths (LeetCode 62)

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., 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.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

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

Example 2:

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

1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

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

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

Type	Value
Time	O(m*n)
Space	O(m*n)

• Approach: Use a 2D array dp where dp[i][j] represents the number of unique paths to reach cell (i, j). The number of paths to (i, j) is the sum of paths from (i-1, j) (above) and (i, j-1) (left).
• Dry run (m=3, n=2):
  • initialize paths in row 0 and col 0 to 1
  • dp = [[1, 1],
    [1, ?],
    [1, ?]]
  • i=1, j=1: dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
  • i=2, j=1: dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
  • result: dp[2][1] = 3

---

Minimum Path Sum (LeetCode 64)

64. Minimum Path Sum

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.

Example 1:

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:

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

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

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]
        for j in range(1, n):
            grid[0][j] += grid[0][j - 1]
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
        return grid[m - 1][n - 1]

Type	Value
Time	O(m*n)
Space	O(1)

• Approach: In-place DP. First accumulate costs along the first column and first row (since there's only one path to reach any cell in row 0 or column 0). Then for each remaining cell, the minimum path sum is the cell's value plus the minimum of the cell above and the cell to the left.
• Dry run (grid = [[1,3,1],[1,5,1],[4,2,1]]):
  • First column: grid[1][0]=1+1=2, grid[2][0]=2+4=6
  • First row: grid[0][1]=1+3=4, grid[0][2]=4+1=5
  • grid[1][1] = 5 + min(4, 2) = 7
  • grid[1][2] = 1 + min(5, 7) = 6
  • grid[2][1] = 2 + min(7, 6) = 8
  • grid[2][2] = 1 + min(6, 8) = 7
  • Return 7.

---

Edit Distance (LeetCode 72)

72. 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

Example 1:

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

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int 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];
    }
}

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            dp[i][0] = i
        for j in range(1, n + 1):
            dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

        return dp[m][n]

Type	Value
Time	O(m*n)
Space	O(m*n)

• Approach: Use a 2D DP array where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2. If the characters match, dp[i][j] = dp[i-1][j-1]. Otherwise, consider insertion (dp[i][j-1]), deletion (dp[i-1][j]), and substitution (dp[i-1][j-1]) and add 1 to the minimum of these.
• Dry run (word1="sea", word2="eat"):
  • Initialize dp: sizes 4x4. dp[i][0] = i, dp[0][j] = j.
  • i=1 ('s'), j=1 ('e'): no match -> min(dp[0][0], dp[1][0], dp[0][1]) + 1 = min(0, 1, 1) + 1 = 1
  • i=1 ('s'), j=2 ('a'): no match -> min(dp[0][1], dp[1][1], dp[0][2]) + 1 = min(1, 1, 2) + 1 = 2
  • i=2 ('e'), j=1 ('e'): match -> dp[1][0] = 1.
  • i=3 ('a'), j=2 ('a'): match -> inherits dp[2][1], which eventually leads to optimal min distance 2.

---

Climbing Stairs (LeetCode 70)

70. 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?

Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for _ in range(3, n + 1):
            curr = prev1 + prev2
            prev2 = prev1
            prev1 = curr
        return prev1

Type	Value
Time	O(n)
Space	O(1)

• Approach: Space-optimized DP. dp[i] = dp[i-1] + dp[i-2]. Track only the last two values.
• Dry run (n = 4):
  • n=1 -> 1, n=2 -> 2
  • i=3: curr = 2 + 1 = 3, prev2=2, prev1=3
  • i=4: curr = 3 + 2 = 5, prev2=3, prev1=5
  • Return 5

---

House Robber (LeetCode 198)

198. 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.

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

Example 2:
Input: nums = [2,7,9,3,1]
Output: 12

class Solution {
    public int rob(int[] nums) {
        int prevRob = 0;
        int maxRob = 0;
        for (int curVal : nums) {
            int temp = Math.max(maxRob, prevRob + curVal);
            prevRob = maxRob;
            maxRob = temp;
        }
        return maxRob;
    }
}

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev_rob = max_rob = 0
        for cur_val in nums:
            temp = max(max_rob, prev_rob + cur_val)
            prev_rob = max_rob
            max_rob = temp
        return max_rob

Type	Value
Time	O(n)
Space	O(1)

• Approach: Dynamic Programming. For each house, we decide to either rob it (adding its value to the maximum amount robbed prior to the previous house) or not rob it (keeping the maximum amount robbed up to the previous house).
• Dry run (nums=[1,2,3,1]):
  • 1 -> temp=max(0, 0+1)=1, prev=0, max=1
  • 2 -> temp=max(1, 0+2)=2, prev=1, max=2
  • 3 -> temp=max(2, 1+3)=4, prev=2, max=4
  • 1 -> temp=max(4, 2+1)=4, prev=4, max=4
  • Result: 4

---

House Robber II (LeetCode 213)

213. 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.

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

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

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

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robber(nums, 0, nums.length - 2), robber(nums, 1, nums.length - 1));
    }
    public int robber(int n[], int s, int e) {
        int prev_rob = 0;
        int max_rob = 0;
        int temp = 0;
        for (int i = s; i <= e; i++){
            temp = Math.max(max_rob, prev_rob + n[i]);
            prev_rob = max_rob;
            max_rob = temp;
        }
        return max_rob;
    }
}

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
            
        def robber(s, e):
            prev_rob = max_rob = 0
            for i in range(s, e + 1):
                temp = max(max_rob, prev_rob + nums[i])
                prev_rob = max_rob
                max_rob = temp
            return max_rob
            
        return max(robber(0, len(nums) - 2), robber(1, len(nums) - 1))

Type	Value
Time	O(n)
Space	O(1)

• Approach: Since the houses are in a circle, we can't rob both the first and the last house. Thus, we solve the basic House Robber problem twice: once from house 0 to n-2, and once from house 1 to n-1. We return the maximum of these two results.
• Dry run (nums=[2,3,2]):
  • robber(0, 1) -> input [2,3] -> max=3
  • robber(1, 2) -> input [3,2] -> max=3
  • max(3, 3) = 3

---

Decode Ways (LeetCode 91)

91. Decode Ways
You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

• "AAJF" with the grouping (1, 1, 10, 6)
• "KJF" with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = "12"

Output: 2

Explanation:

"12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"

Output: 3

Explanation:

"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"

Output: 0

Explanation:

"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
        int n = s.length();
        int twoBack = 1; 
        int oneBack = 1; 
        for (int i = 2; i <= n; i++) {
            int current = 0;
            int oneDigit = s.charAt(i - 1) - '0';
            if (oneDigit != 0) {
                current += oneBack;
            }
            int twoDigit = (s.charAt(i - 2) - '0') * 10 + oneDigit;
            if (twoDigit >= 10 && twoDigit <= 26) {
                current += twoBack;
            }

            twoBack = oneBack;
            oneBack = current;
        }

        return oneBack;
    }
}

---

Longest Common Subsequence (LeetCode 1143)

1143. 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.

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

Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    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[m][n];
    }
}

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]

Type	Value
Time	O(m*n)
Space	O(m*n)

• Approach: 2D Dynamic Programming. If characters match text1[i-1] == text2[j-1], dp[i][j] = 1 + dp[i-1][j-1]. Otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
• Dry run (text1 = "abcde", text2 = "ace"):
  • i=1 ('a'), j=1 ('a'): match -> dp[1][1] = 1 + dp[0][0] = 1
  • i=2 ('b'), j=1 ('a'): no match -> max(dp[1][1], dp[2][0]) = 1
  • i=3 ('c'), j=2 ('c'): match -> dp[3][2] = 1 + dp[2][1] = 2
  • i=5 ('e'), j=3 ('e'): match -> dp[5][3] = 1 + dp[4][2] = 3
  • Returns 3

---

Longest Palindromic Subsequence (LeetCode 516)

516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s.

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

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[0][n - 1];
    }
}

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i + 1][j - 1]
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return dp[0][n - 1]

Type	Value
Time	O(n²)
Space	O(n²)

• Approach: Use a 2D DP table where dp[i][j] represents the length of the longest palindromic subsequence in s[i..j]. If s[i] == s[j], extend by 2 from dp[i+1][j-1]. Otherwise, take the max of dp[i+1][j] and dp[i][j-1]. Fill the table from bottom-right to top-left.
• Dry run (s = "bbbab"):
  • All single chars: dp[i][i] = 1
  • i=3, j=4: 'a' != 'b' → max(dp[4][4], dp[3][3]) = 1
  • i=2, j=3: 'b' != 'a' → 1, j=4: 'b' == 'b' → 2 + dp[3][3] = 3
  • Continuing... dp[0][4] = 4

class Solution {
    public String longestPalindromeSubseq(String s) {

        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i = n - 1; i >= 0; i--){
            dp[i][i] = 1;
            for(int j = i + 1; j < n; j++){
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = 2 + (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0);
                else
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        char[] ans = new char[dp[0][n - 1]];
        int i = 0, j = n - 1;
        int left = 0, right = ans.length - 1;
        while(i <= j){
            if(i == j){
                ans[left] = s.charAt(i);
                break;
            }
            if(s.charAt(i) == s.charAt(j)){
                ans[left++] = s.charAt(i);
                ans[right--] = s.charAt(j);
                i++;
                j--;
            }
            else if(dp[i + 1][j] >= dp[i][j - 1]){
                i++;
            }
            else{
                j--;
            }
        }
        return new String(ans);
    }
}

---

Word Break (LeetCode 139)

139. 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.

Example 1:

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

Example 2:

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

import java.util.*;
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        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()];
    }
}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        return dp[len(s)]

Type	Value
Time	O(n²)
Space	O(n)

• Approach: Use DP. dp[i] is true if s[0..i-1] can be segmented. For each position i, check all substrings s[j..i] — if dp[j] is true and substring is in dict, set dp[i] = true.
• Dry run (s = "leetcode", wordDict = ["leet","code"]):
  • dp[0]=true
  • i=4: j=0, dp[0]=true, s[0..4]="leet" in dict → dp[4]=true
  • i=8: j=4, dp[4]=true, s[4..8]="code" in dict → dp[8]=true
  • Return dp[8] = true

---

Coin Change Ways (LeetCode 518)

518. Coin Change II

Given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money, return the number of combinations that make up that amount.

Example:

Input: coins = [1, 2, 5], amount = 5
Output: 4
Explanation: There are 4 ways to make up amount 5: [5], [2,2,1], [2,1,1,1], [1,1,1,1,1].

public class CoinChangeWays {
    public static int countWays(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

class CoinChangeWays:
    def countWays(self, coins: List[int], amount: int) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]
        return dp[amount]

Type	Value
Time	O(n * amount)
Space	O(amount)

• Approach: Use a 1D DP array where dp[i] represents the number of ways to make amount i. For each coin, iterate through all amounts from coin to amount and add dp[i - coin] to dp[i].
• Dry run (coins={1,2,5}, amount=5):
  • start: [1,0,0,0,0,0]
  • coin=1 → [1,1,1,1,1,1]
  • coin=2 → [1,1,2,2,3,3]
  • coin=5 → [1,1,2,2,3,4] → ways=4

---