Unique Paths II (With Obstacles)

🎯

Unique Paths II (With Obstacles)

mediumDPAmazonGoogle

Imagine a robot navigating a grid warehouse floor where some tiles are blocked by crates. How many ways can it reach the destination without hitting obstacles?

💡 This problem asks for counting paths in a grid with obstacles. Beginners often struggle because they try to count paths without considering blocked cells, or they get confused about how to handle the first row and column when obstacles appear.

📋

Problem Statement

Given an m x n grid filled with 0's (empty cells) and 1's (obstacles), find the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1,n-1). You can only move either down or right at any point in time. Return 0 if there is no valid path.

1 ≤ m, n ≤ 100grid[i][j] is either 0 or 1The starting and ending cells are always within the grid

💡

Example

Input"[[0,0,0],[0,1,0],[0,0,0]]"

Output2

There are two paths avoiding the obstacle at position (1,1): right->right->down->down and down->down->right->right.

• Grid with only one cell and no obstacle → output 1
• Grid with only one cell and obstacle → output 0
• Obstacle at starting cell → output 0
• Obstacle at ending cell → output 0
• Grid where entire first row or first column is blocked → output 0

🔁

Why DP?

Why greedy fails:

A greedy approach that always tries to move right or down without considering obstacles ahead can fail. For example, if the path to the right is blocked but going down first then right is possible, greedy would miss the valid path.

DP state:

dp[i][j] represents the number of unique paths to reach cell (i, j) from the start (0, 0) without hitting obstacles.

Recurrence:dp[i][j] = 0 if obstacle at (i,j); else dp[i][j] = dp[i-1][j] + dp[i][j-1]

If the current cell is blocked, no paths lead here. Otherwise, paths come from above and left cells.

⚠️

Common Mistakes

Not handling obstacle at start cell

Returns non-zero paths incorrectly

✅ Initialize dp[0][0] = 0 if obstacleGrid[0][0] == 1

Not resetting dp cell to 0 when obstacle encountered

Paths count incorrectly accumulates through obstacles

✅ Set dp[i][j] = 0 if obstacleGrid[i][j] == 1

Incorrectly initializing first row and column

Paths count propagates incorrectly past obstacles

✅ Carefully initialize first row and column considering obstacles

Using dp[j-1] before it is updated in 1D DP

Incorrect path counts due to wrong dependency order

✅ Iterate columns left to right so dp[j-1] is updated before dp[j]

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive solutions are inefficient.

Intuition

Count paths by recursively exploring moves down and right, stopping if hitting obstacles or boundaries.

Algorithm

1. Start at cell (0,0).
2. If current cell is obstacle or out of bounds, return 0.
3. If current cell is bottom-right, return 1.
4. Recursively count paths from cell below and cell to the right.
5. Sum these counts to get total paths from current cell.

💡 This approach is intuitive but inefficient because it recomputes paths for the same cells multiple times.

Recurrence:f(i,j) = 0 if obstacle or out of bounds; 1 if (i,j) is destination; else f(i+1,j) + f(i,j+1)

</>

Code

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    def dfs(i, j):
        if i >= m or j >= n or obstacleGrid[i][j] == 1:
            return 0
        if i == m - 1 and j == n - 1:
            return 1
        return dfs(i + 1, j) + dfs(i, j + 1)

    return dfs(0, 0)

# Example usage:
if __name__ == '__main__':
    grid = [[0,0,0],[0,1,0],[0,0,0]]
    print(uniquePathsWithObstacles(grid))  # Output: 2

Line Notes

def dfs(i, j):Defines recursive helper to count paths from cell (i,j)

if i >= m or j >= n or obstacleGrid[i][j] == 1:Stops recursion if out of bounds or obstacle encountered

if i == m - 1 and j == n - 1:Base case: reached destination, count as one path

return dfs(i + 1, j) + dfs(i, j + 1)Sum paths from down and right neighbors

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return dfs(obstacleGrid, 0, 0);
    }
    private int dfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if (i >= m || j >= n || grid[i][j] == 1) return 0;
        if (i == m - 1 && j == n - 1) return 1;
        return dfs(grid, i + 1, j) + dfs(grid, i, j + 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{0,0,0},{0,1,0},{0,0,0}};
        System.out.println(sol.uniquePathsWithObstacles(grid)); // 2
    }
}

Line Notes

public int uniquePathsWithObstacles(int[][] obstacleGrid)Entry method calling recursive dfs

if (i >= m || j >= n || grid[i][j] == 1) return 0;Stop if out of bounds or obstacle

if (i == m - 1 && j == n - 1) return 1;Base case: reached destination

return dfs(grid, i + 1, j) + dfs(grid, i, j + 1);Sum paths from down and right

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        return dfs(grid, 0, 0);
    }
private:
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size(), n = grid[0].size();
        if (i >= m || j >= n || grid[i][j] == 1) return 0;
        if (i == m - 1 && j == n - 1) return 1;
        return dfs(grid, i + 1, j) + dfs(grid, i, j + 1);
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,0,0},{0,1,0},{0,0,0}};
    cout << sol.uniquePathsWithObstacles(grid) << endl; // 2
    return 0;
}

Line Notes

int dfs(vector<vector<int>>& grid, int i, int j)Recursive helper counting paths from (i,j)

if (i >= m || j >= n || grid[i][j] == 1) return 0;Stop recursion if invalid or blocked

if (i == m - 1 && j == n - 1) return 1;Base case: reached destination

return dfs(grid, i + 1, j) + dfs(grid, i, j + 1);Sum paths from down and right neighbors

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length, n = obstacleGrid[0].length;
    function dfs(i, j) {
        if (i >= m || j >= n || obstacleGrid[i][j] === 1) return 0;
        if (i === m - 1 && j === n - 1) return 1;
        return dfs(i + 1, j) + dfs(i, j + 1);
    }
    return dfs(0, 0);
};

// Example usage:
console.log(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])); // 2

Line Notes

function dfs(i, j)Recursive function to count paths from (i,j)

if (i >= m || j >= n || obstacleGrid[i][j] === 1) return 0;Stop if out of bounds or obstacle

if (i === m - 1 && j === n - 1) return 1;Base case: reached destination

return dfs(i + 1, j) + dfs(i, j + 1);Sum paths from down and right

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

Each cell branches into two recursive calls, leading to exponential time.

💡 For a 10x10 grid, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem structure.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing paths for the same cell, drastically improving efficiency.

Intuition

Store results of subproblems (paths from each cell) so repeated calls return cached results.

Algorithm

1. Initialize a memo table to store results for each cell.
2. Recursively compute paths from (0,0), returning cached results if available.
3. If cell is obstacle or out of bounds, return 0.
4. If destination reached, return 1.
5. Sum memoized results from down and right neighbors.

💡 Memoization turns exponential recursion into polynomial by avoiding duplicate work.

Recurrence:f(i,j) = 0 if obstacle or out of bounds; 1 if destination; else memo[i][j] = f(i+1,j) + f(i,j+1)

</>

Code

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    memo = [[-1]*n for _ in range(m)]
    def dfs(i, j):
        if i >= m or j >= n or obstacleGrid[i][j] == 1:
            return 0
        if i == m - 1 and j == n - 1:
            return 1
        if memo[i][j] != -1:
            return memo[i][j]
        memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1)
        return memo[i][j]

    return dfs(0, 0)

# Example usage:
if __name__ == '__main__':
    grid = [[0,0,0],[0,1,0],[0,0,0]]
    print(uniquePathsWithObstacles(grid))  # Output: 2

Line Notes

memo = [[-1]*n for _ in range(m)]Initialize memo table with -1 indicating uncomputed cells

if memo[i][j] != -1:Return cached result if already computed

memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1)Store computed paths count for reuse

return memo[i][j]Return memoized result

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] memo = new int[m][n];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dfs(obstacleGrid, 0, 0, memo);
    }
    private int dfs(int[][] grid, int i, int j, int[][] memo) {
        int m = grid.length, n = grid[0].length;
        if (i >= m || j >= n || grid[i][j] == 1) return 0;
        if (i == m - 1 && j == n - 1) return 1;
        if (memo[i][j] != -1) return memo[i][j];
        memo[i][j] = dfs(grid, i + 1, j, memo) + dfs(grid, i, j + 1, memo);
        return memo[i][j];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{0,0,0},{0,1,0},{0,0,0}};
        System.out.println(sol.uniquePathsWithObstacles(grid)); // 2
    }
}

Line Notes

int[][] memo = new int[m][n];Create memo table for caching

for (int[] row : memo) Arrays.fill(row, -1);Initialize memo with -1 to mark unvisited

if (memo[i][j] != -1) return memo[i][j];Return cached result if available

memo[i][j] = dfs(grid, i + 1, j, memo) + dfs(grid, i, j + 1, memo);Store computed paths count

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        return dfs(grid, 0, 0, memo);
    }
private:
    int dfs(vector<vector<int>>& grid, int i, int j, vector<vector<int>>& memo) {
        int m = grid.size(), n = grid[0].size();
        if (i >= m || j >= n || grid[i][j] == 1) return 0;
        if (i == m - 1 && j == n - 1) return 1;
        if (memo[i][j] != -1) return memo[i][j];
        memo[i][j] = dfs(grid, i + 1, j, memo) + dfs(grid, i, j + 1, memo);
        return memo[i][j];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,0,0},{0,1,0},{0,0,0}};
    cout << sol.uniquePathsWithObstacles(grid) << endl; // 2
    return 0;
}

Line Notes

vector<vector<int>> memo(m, vector<int>(n, -1));Initialize memo table with -1

if (memo[i][j] != -1) return memo[i][j];Return cached result if computed

memo[i][j] = dfs(grid, i + 1, j, memo) + dfs(grid, i, j + 1, memo);Store computed paths count

return memo[i][j];Return memoized value

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length, n = obstacleGrid[0].length;
    const memo = Array.from({length: m}, () => Array(n).fill(-1));
    function dfs(i, j) {
        if (i >= m || j >= n || obstacleGrid[i][j] === 1) return 0;
        if (i === m - 1 && j === n - 1) return 1;
        if (memo[i][j] !== -1) return memo[i][j];
        memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1);
        return memo[i][j];
    }
    return dfs(0, 0);
};

// Example usage:
console.log(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])); // 2

Line Notes

const memo = Array.from({length: m}, () => Array(n).fill(-1));Create memo table initialized with -1

if (memo[i][j] !== -1) return memo[i][j];Return cached result if available

memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1);Store computed paths count

return memo[i][j];Return memoized value

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) for memo and recursion stack

Each cell is computed once and cached, reducing exponential calls to polynomial.

💡 For a 100x100 grid, this means 10,000 computations, which is efficient.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for interview constraints.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively, which is often easier to debug and preferred in interviews.

Intuition

Fill a dp table row by row, where each cell's value is sum of paths from top and left, skipping obstacles.

Algorithm

1. Create a dp table same size as grid initialized to 0.
2. Set dp[0][0] to 1 if start is not obstacle, else 0.
3. Iterate over each cell row-wise and column-wise.
4. If cell is obstacle, dp[i][j] = 0.
5. Else dp[i][j] = dp[i-1][j] + dp[i][j-1] (if indices valid).
6. Return dp[m-1][n-1] as result.

💡 This approach explicitly builds the solution bottom-up, ensuring all dependencies are computed before use.

Recurrence:dp[i][j] = 0 if obstacle; else dp[i][j] = dp[i-1][j] + dp[i][j-1]

</>

Code

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            else:
                if i > 0:
                    dp[i][j] += dp[i-1][j]
                if j > 0:
                    dp[i][j] += dp[i][j-1]
    return dp[m-1][n-1]

# Example usage:
if __name__ == '__main__':
    grid = [[0,0,0],[0,1,0],[0,0,0]]
    print(uniquePathsWithObstacles(grid))  # Output: 2

Line Notes

dp = [[0]*n for _ in range(m)]Initialize dp table with zeros

dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0Set start cell paths to 1 if not blocked

if obstacleGrid[i][j] == 1: dp[i][j] = 0No paths if obstacle present

dp[i][j] += dp[i-1][j] / dp[i][j-1]Add paths from top and left neighbors if valid

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    if (i > 0) dp[i][j] += dp[i-1][j];
                    if (j > 0) dp[i][j] += dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{0,0,0},{0,1,0},{0,0,0}};
        System.out.println(sol.uniquePathsWithObstacles(grid)); // 2
    }
}

Line Notes

int[][] dp = new int[m][n];Create dp table for storing path counts

dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;Initialize start cell paths

if (obstacleGrid[i][j] == 1) dp[i][j] = 0;Set zero paths for obstacles

dp[i][j] += dp[i-1][j]; dp[i][j] += dp[i][j-1];Add paths from top and left neighbors

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = grid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    if (i > 0) dp[i][j] += dp[i-1][j];
                    if (j > 0) dp[i][j] += dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,0,0},{0,1,0},{0,0,0}};
    cout << sol.uniquePathsWithObstacles(grid) << endl; // 2
    return 0;
}

Line Notes

vector<vector<int>> dp(m, vector<int>(n, 0));Initialize dp table with zeros

dp[0][0] = grid[0][0] == 0 ? 1 : 0;Set start cell paths to 1 if not blocked

if (grid[i][j] == 1) dp[i][j] = 0;No paths if obstacle present

dp[i][j] += dp[i-1][j]; dp[i][j] += dp[i][j-1];Add paths from top and left neighbors

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length, n = obstacleGrid[0].length;
    const dp = Array.from({length: m}, () => Array(n).fill(0));
    dp[0][0] = obstacleGrid[0][0] === 0 ? 1 : 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[i][j] = 0;
            } else {
                if (i > 0) dp[i][j] += dp[i-1][j];
                if (j > 0) dp[i][j] += dp[i][j-1];
            }
        }
    }
    return dp[m-1][n-1];
};

// Example usage:
console.log(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])); // 2

Line Notes

const dp = Array.from({length: m}, () => Array(n).fill(0));Create dp table initialized with zeros

dp[0][0] = obstacleGrid[0][0] === 0 ? 1 : 0;Initialize start cell paths

if (obstacleGrid[i][j] === 1) dp[i][j] = 0;Set zero paths for obstacles

dp[i][j] += dp[i-1][j]; dp[i][j] += dp[i][j-1];Add paths from top and left neighbors

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill each cell once, summing paths from neighbors.

💡 For a 100x100 grid, this means 10,000 operations, which is efficient and fast.

Interview Verdict: Accepted

This is the standard DP solution preferred in interviews for clarity and efficiency.

🧠

Space Optimized Bottom-Up DP (1D DP Array)

💡 Since dp[i][j] depends only on dp[i-1][j] and dp[i][j-1], we can use a single 1D array to save space.

Intuition

Use one array to represent the current row's path counts, updating it as we move through the grid.

Algorithm

1. Initialize a 1D dp array of length n with zeros.
2. Set dp[0] to 1 if start cell is not obstacle, else 0.
3. Iterate over each row and column.
4. If current cell is obstacle, set dp[j] = 0.
5. Else update dp[j] += dp[j-1] if j > 0.
6. After processing all rows, dp[n-1] holds the result.

💡 This approach reduces space from O(m*n) to O(n) by reusing the dp array for each row.

Recurrence:dp[j] = 0 if obstacle; else dp[j] += dp[j-1]

</>

Code

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0]*n
    dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0
            else:
                if j > 0:
                    dp[j] += dp[j-1]
    return dp[-1]

# Example usage:
if __name__ == '__main__':
    grid = [[0,0,0],[0,1,0],[0,0,0]]
    print(uniquePathsWithObstacles(grid))  # Output: 2

Line Notes

dp = [0]*nInitialize 1D dp array for current row

dp[0] = 1 if obstacleGrid[0][0] == 0 else 0Set start cell paths

if obstacleGrid[i][j] == 1: dp[j] = 0Reset paths to zero if obstacle

dp[j] += dp[j-1]Add paths from left neighbor in current row

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{0,0,0},{0,1,0},{0,0,0}};
        System.out.println(sol.uniquePathsWithObstacles(grid)); // 2
    }
}

Line Notes

int[] dp = new int[n];Create 1D dp array for current row

dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;Initialize start cell paths

if (obstacleGrid[i][j] == 1) dp[j] = 0;Reset paths to zero if obstacle

dp[j] += dp[j - 1];Add paths from left neighbor

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n, 0);
        dp[0] = grid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,0,0},{0,1,0},{0,0,0}};
    cout << sol.uniquePathsWithObstacles(grid) << endl; // 2
    return 0;
}

Line Notes

vector<int> dp(n, 0);Initialize 1D dp array

dp[0] = grid[0][0] == 0 ? 1 : 0;Set start cell paths

if (grid[i][j] == 1) dp[j] = 0;Reset paths to zero if obstacle

dp[j] += dp[j - 1];Add paths from left neighbor

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length, n = obstacleGrid[0].length;
    const dp = new Array(n).fill(0);
    dp[0] = obstacleGrid[0][0] === 0 ? 1 : 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
};

// Example usage:
console.log(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])); // 2

Line Notes

const dp = new Array(n).fill(0);Initialize 1D dp array

dp[0] = obstacleGrid[0][0] === 0 ? 1 : 0;Set start cell paths

if (obstacleGrid[i][j] === 1) dp[j] = 0;Reset paths to zero if obstacle

dp[j] += dp[j - 1];Add paths from left neighbor

⏱

Complexity

TimeO(m*n)

SpaceO(n)

We use a single array updated row by row, saving space while maintaining correctness.

💡 For a 100x100 grid, this reduces memory from 10,000 ints to 100 ints.

Interview Verdict: Accepted

This is the most space-efficient DP solution and preferred when memory is constrained.

📊

All Approaches - One-Glance Tradeoffs

💡 Bottom-up DP with space optimization is best for interviews; memoization is good backup; brute force only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes	No	Mention only - never code
2. Top-Down DP with Memoization	O(m*n)	O(m*n)	Possible but unlikely for constraints	Yes	Good if comfortable with recursion
3. Bottom-Up DP (Tabulation)	O(m*n)	O(m*n)	No	Yes	Preferred standard solution
4. Space Optimized Bottom-Up DP	O(m*n)	O(n)	No	No (without extra info)	Best for memory constrained scenarios

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to grasp recursion, then optimize stepwise.

How to Present

Clarify problem constraints and obstacle handling.Explain brute force recursion and its inefficiency.Introduce memoization to optimize overlapping subproblems.Present bottom-up DP for iterative clarity.Finally, discuss space optimization if time permits.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, handling edge cases, and writing clean code.

Common Follow-ups

• What if moves can be up or left? → Modify DP accordingly.
• How to reconstruct one path? → Store parent pointers during DP.

💡 These follow-ups test flexibility and deeper understanding of DP and path reconstruction.

🔍

Pattern Recognition

When to Use

1) Grid or matrix input 2) Counting paths or sequences 3) Obstacles or blocked cells present 4) Moves restricted to right/down

Signature Phrases

unique pathsobstaclemove only right or downcount number of ways

NOT This Pattern When

Problems involving arbitrary moves or no obstacles are simpler and may not require obstacle handling logic.

Similar Problems

Unique Paths I - same problem without obstaclesMinimum Path Sum - similar grid traversal with costsRobot Paths with Obstacles - variant with different constraints

Practice

1. Consider the following snippet from the optimal Zuma Game solution. Given board = "WRRBBW" and hand = "RB", what is the return value of findMinStep(board, hand)?

easy

A. 2

B. -1

C. 3

D. 1

Solution

1. Step 1: Trace initial calls with board="WRRBBW" and hand="RB"

   Hand has 1 R and 1 B. The board requires more balls to clear groups of 3, but hand is insufficient to clear all.

2. Step 2: Check if any insertion sequence clears board

   Trying to insert R or B balls to form groups of 3 fails due to insufficient balls; no sequence clears the board fully.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Return -1 indicates no solution with given hand [OK]

Hint: Insufficient hand balls cause no solution -> -1 [OK]

Common Mistakes:

• Assuming partial removals suffice to clear board
• Miscounting balls needed for group removal
• Forgetting to restore hand counts after recursion

2. The following code attempts to compute the minimum falling path sum using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]

    for i in range(1, n):
        for j in range(n):
            best = dp[j]
            if j > 0:
                best = min(best, dp[j-1])
            if j < n - 1:
                best = min(best, dp[j+1])
            dp[j] = matrix[i][j] + best

    return min(dp)

medium

A. Line 7: Updating dp[j] inside the inner loop without backup

B. Line 9: Checking if j > 0 before accessing dp[j-1]

C. Line 3: dp initialization with matrix[0][:]

D. Line 12: Returning min(dp) after the loops

Solution

1. Step 1: Understand dp update logic

   dp array holds minimum sums for previous row. Updating dp[j] in place overwrites values needed for neighbors in the same iteration.

2. Step 2: Identify the bug

   Updating dp[j] inside the inner loop without using a separate array causes premature overwriting, leading to incorrect neighbor comparisons.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using a separate new_dp array fixes the bug [OK]

Hint: Don't overwrite dp while still reading from it in same iteration [OK]

Common Mistakes:

• Updating dp in place without backup
• Ignoring boundary checks

3. The following code attempts to solve the Strange Printer problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on inputs like "aba"?

medium

A. Line 18: dp[i][j] = dp[i][j - 1] + 1 assignment

B. Line 13: dp[i][i] = 1 initialization

C. Line 4: compressed.append(c) without checking for duplicates

D. Line 21: if s[k] == s[j] condition

Solution

1. Step 1: Identify compression step

   Line 4 appends every character without checking if it equals the last compressed character, so no compression occurs.

2. Step 2: Understand impact of missing compression

   Without compression, the DP runs on the full string length, causing inefficiency and possibly incorrect merges, especially on inputs like "aba" where compression reduces complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Compression step must skip duplicates to optimize DP [OK]

Hint: Compression must skip consecutive duplicates to avoid TLE and errors [OK]

Common Mistakes:

• Forgetting to compress string before DP

4. What is the time complexity of the optimal interval DP solution for Zuma Game (Min Moves to Clear) with board length n and hand size m, considering the state space and transitions?

medium

A. O(n^4 * m^5)

B. O(n^2 * m^3)

C. O(n^3 * m^4)

D. O(5^(n+m))

Solution

1. Step 1: Identify DP state dimensions

   The DP state depends on intervals of the board (O(n^2)) and hand counts (up to 5 colors, each up to m), leading to O(n^3 * m^4) states due to interval splits and hand count combinations.

2. Step 2: Analyze transitions and recursion

   Each state considers splits and insertions, adding an extra factor of n and m, resulting in O(n^3 * m^4) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Complexity matches known analysis for interval DP with hand states [OK]

Hint: Interval splits and hand states multiply complexity [OK]

Common Mistakes:

• Confusing n^2 intervals with n^3 due to splits
• Ignoring hand state dimension leading to underestimation
• Mistaking brute force complexity for DP complexity

5. Suppose the Burst Balloons problem is modified so that each balloon can be burst multiple times (reused), and bursting a balloon again yields coins based on the current adjacent balloons. Which of the following changes to the bottom-up DP approach correctly adapts to this variant?

hard

A. Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts

B. Modify the DP to consider only the first burst of each balloon and ignore reuse

C. Use the same interval DP but allow k to be chosen multiple times per interval

D. Use a greedy approach bursting the balloon with the maximum product of neighbors repeatedly

Solution

1. Step 1: Understand reuse impact

   Allowing multiple bursts per balloon means the problem state must track how many times each balloon has been burst, increasing complexity.

2. Step 2: Adapt DP state

   Interval DP assuming each balloon bursts once no longer works. We need a DP or memoization that tracks burst counts per balloon to correctly compute coins.

3. Step 3: Evaluate options

   Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts correctly proposes a stateful DP with counts and memoization. Use the same interval DP but allow k to be chosen multiple times per interval incorrectly reuses interval DP without state changes. Modify the DP to consider only the first burst of each balloon and ignore reuse ignores reuse, and D is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking burst counts is necessary for reuse variants [OK]

Hint: Reuse requires tracking burst counts, not just intervals [OK]

Common Mistakes:

• Trying naive interval DP for reuse
• Ignoring state explosion
• Using greedy for complex DP variants