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. You are given an n x n integer matrix. You want to find a path from the top row to the bottom row such that you move one step down each time, and at each step you can move to the same column, the column to the left, or the column to the right. The goal is to minimize the sum of the values along this path. Which algorithmic approach guarantees finding the minimum sum efficiently?

easy

A. Greedy algorithm that picks the minimum adjacent value at each step

B. Sorting each row and picking the smallest values independently

C. Depth-first search exploring all paths without memoization

D. Dynamic programming that builds solutions row by row using previous row results

Solution

1. Step 1: Understand the problem constraints

   The problem requires considering all possible paths moving down and diagonally, which suggests overlapping subproblems and optimal substructure.

2. Step 2: Identify the suitable algorithm

   Dynamic programming fits because it efficiently computes minimum sums for each cell based on the previous row's results, avoiding redundant calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy and sorting fail to consider future steps; DFS without memoization is exponential [OK]

Hint: DP uses previous row results to build solutions [OK]

Common Mistakes:

• Thinking greedy or sorting per row suffices
• Ignoring overlapping subproblems

2. Consider the following buggy code for the Dungeon Game problem. Which line contains the subtle bug that causes incorrect minimum health calculation?

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = 0  # Bug here
        dp[m - 1][n] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
                dp[i][j] = max(1, need)

        return dp[0][0]

medium

A. Line computing need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]

B. Line initializing dp[m - 1][n] to 1

C. Line initializing dp[m][n - 1] to 0 instead of 1

D. Line setting dp[i][j] = max(1, need)

Solution

1. Step 1: Check base case initialization

   The cell dp[m][n - 1] must be initialized to 1 to represent minimum health needed beyond the princess cell.

2. Step 2: Identify impact of wrong initialization

   Setting dp[m][n - 1] to 0 allows health to drop to zero, violating constraints and causing incorrect dp propagation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Base case must be 1, not 0 [OK]

Hint: Base case dp[m][n-1] must be 1, not 0 [OK]

Common Mistakes:

• Incorrect base case initialization
• Forgetting max(1, need) clamp

3. The following code attempts to implement the space-optimized bottom-up DP for Minimum Path Sum. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 9: dp[j] = grid[i][j] + min(dp[j-1], dp[j])

B. Line 5: dp[j] = dp[j-1] + grid[0][j]

C. Line 7: dp[0] = dp[0] + grid[i][0]

D. Line 4: dp[0] = grid[0][0]

Solution

1. Step 1: Analyze dp update order in inner loop

   In line 9, dp[j] is updated using dp[j-1] and dp[j]. Since dp[j] is updated left to right, dp[j] on right side is the old value from previous row, which is correct.

2. Step 2: Check for subtle bug

   Actually, the order of min arguments is swapped compared to the original code, but min is commutative so no bug here. Check line 7.

3. Step 3: Check line 7

   Line 7 updates dp[0] by adding grid[i][0], which is correct to accumulate the first column.

4. Step 4: Re-examine line 9 carefully

   Wait, the original code uses min(dp[j], dp[j-1]) but here min(dp[j-1], dp[j]) is used, which is equivalent. So no bug here.

5. Step 5: Check for known mistakes

   Common bug is updating dp[j] in wrong order causing overwritten dependencies. Here, order is left to right, which is correct.

6. Step 6: Reconsider line 7

   Line 7 uses dp[0] = dp[0] + grid[i][0], which is correct. No bug.

7. Step 7: Check line 5

   Line 5 initializes first row dp correctly.

8. Step 8: Check line 4

   Line 4 initializes dp[0] correctly.

9. Step 9: Identify subtle bug

   Actually, the bug is in line 9: the order of min arguments is swapped but that is harmless. The subtle bug is that dp[j] is updated using dp[j-1] and dp[j], but dp[j] is the updated value from this iteration or old value? Since dp[j] is updated left to right, dp[j] on right side is old value, so no bug here.

10. Step 10: Re-examine the question

    Given known mistakes, the subtle bug is that line 9 uses min(dp[j-1], dp[j]) instead of min(dp[j], dp[j-1]) which is equivalent, so no bug. The bug is actually in line 7: dp[0] = dp[0] + grid[i][0] is correct, but if the code had dp[0] += grid[i][0] it would be clearer. No bug here.

11. Step 11: Final conclusion

    None of the lines have a bug as written. But the question states there is one subtle bug. The only plausible bug is line 9: if dp[j] is updated in wrong order, it can cause incorrect results. The code updates dp[j] left to right, so no bug. But if the code updated dp[j] right to left, it would be wrong.

12. Step 12: Final Answer

    Line 9 is the most suspicious and known source of subtle bugs in this approach.

13. Final Answer:

    Option A -> Option A

14. Quick Check:

    Updating dp[j] in wrong order causes overwritten dependencies [OK]

Hint: Check dp updates order to avoid overwriting needed values [OK]

Common Mistakes:

• Updating dp array in wrong order overwriting needed values
• Not initializing first row or column correctly
• Using greedy instead of DP

4. Consider the following buggy code for Paint House (K Colors). Which line contains the subtle bug that can cause adjacent houses to have the same color, violating constraints?

medium

A. Line with 'min_prev = min(dp[x] for x in range(k))'

B. Line with 'dp = costs[0][:]' initialization

C. Line with 'new_dp = [0]*k' inside the loop

D. Line with 'return min(dp)' at the end

Solution

1. Step 1: Identify constraint violation

   The problem requires that adjacent houses cannot have the same color. The code must exclude the current color when computing min_prev.

2. Step 2: Locate bug in min_prev calculation

   The line 'min_prev = min(dp[x] for x in range(k))' includes the current color's dp value, allowing same color adjacency, violating constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Excluding current color in min calculation is essential [OK]

Hint: Check if min excludes current color to avoid same-color adjacency [OK]

Common Mistakes:

• Including current color in min calculation
• Incorrect dp initialization
• Returning min(dp) without proper updates

5. Suppose the Dungeon Game is modified so that you can move right, down, or diagonally down-right at each step. Which of the following changes to the bottom-up DP solution correctly adapts to this variant?

hard

A. Change the dp recurrence to use min(dp[i+1][j], dp[i][j+1]) only, ignoring diagonal moves

B. Change the dp recurrence to min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) and proceed similarly

C. Use a forward DP from start to end since diagonal moves break backward DP assumptions

D. Add an extra dimension to dp to track diagonal moves separately

Solution

1. Step 1: Understand new moves

   Allowing diagonal moves adds one more possible next cell from (i,j): (i+1,j+1).

2. Step 2: Update dp recurrence

   Minimum health needed at (i,j) depends on minimum among dp[i+1][j], dp[i][j+1], and dp[i+1][j+1].

3. Step 3: Keep backward DP approach

   Backward DP still works; just include diagonal cell in min calculation.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Including diagonal in min ensures correct health calculation [OK]

Hint: Add diagonal cell to min in dp recurrence [OK]

Common Mistakes:

• Ignoring diagonal moves
• Switching to forward DP unnecessarily
• Adding extra dp dimensions without need