Unique Paths II (With Obstacles)

📋

Problem

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?

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

Edge cases: Grid with only one cell and no obstacle → output 1Grid with only one cell and obstacle → output 0Obstacle at starting cell → output 0

</>

IDE

def uniquePathsWithObstacles(obstacleGrid: list[list[int]]) -> int:public int uniquePathsWithObstacles(int[][] obstacleGrid)int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)function uniquePathsWithObstacles(obstacleGrid)

def uniquePathsWithObstacles(obstacleGrid):
    # Write your solution here
    pass

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    // Write your solution here
    return 0;
}

function uniquePathsWithObstacles(obstacleGrid) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Greedy approach returning a single path count ignoring obstacles blocking other routes.✅ Use full DP to sum all valid paths from top-left to bottom-right, not just one path.

Wrong: 0Incorrectly returning 0 when start or end cell is not checked properly for obstacles.✅ Add explicit checks for obstacleGrid[0][0] and obstacleGrid[m-1][n-1] before DP computation.

Wrong: Non-zero when end cell blockedFailing to check obstacle at destination cell, counting paths that end on obstacle.✅ Return 0 immediately if obstacleGrid[m-1][n-1] == 1.

Wrong: TLEUsing brute force recursion without memoization or DP on large inputs.✅ Implement bottom-up DP with O(m*n) time complexity.

✓

Test Cases

Focus on handling grids with minimal size and obstacles at critical positions.

Think about why greedy or partial DP approaches fail on complex obstacle layouts.

Optimize your solution to O(m*n) time complexity to handle large grids efficiently.

t1_01basic

Input{"obstacleGrid":[[0,0,0],[0,1,0],[0,0,0]]}

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Consider dynamic programming to count paths avoiding obstacles.

💡 Use a 2D dp array where dp[i][j] = number of ways to reach cell (i,j).

💡 Initialize dp[0][0] = 1 if no obstacle; dp[i][j] = 0 if obstacle; else dp[i][j] = dp[i-1][j] + dp[i][j-1].

Why it failed: Returned incorrect path count; likely missed obstacle checks or incorrect dp initialization. Fix by setting dp[i][j] = 0 if obstacleGrid[i][j] == 1 and properly summing dp[i-1][j] and dp[i][j-1].

✓ Correctly counts unique paths avoiding obstacles.

t1_02basic

Input{"obstacleGrid":[[0,1],[0,0]]}

Expected1

⏱ Performance - must finish in 2000ms

Only one path: down then right, since (0,1) is blocked.

💡 Check how obstacles block paths in the first row and column.

💡 Remember dp[i][j] = 0 if obstacleGrid[i][j] == 1, else sum of dp from top and left.

💡 Ensure dp initialization handles first row and column correctly when obstacles present.

Why it failed: Incorrect count due to ignoring obstacle in first row blocking right moves. Fix by initializing dp first row and column with zeros after obstacle.

✓ Correctly handles obstacles blocking first row or column.

t2_01edge

Input{"obstacleGrid":[[0]]}

Expected1

⏱ Performance - must finish in 2000ms

Single cell grid with no obstacle has exactly one path (start is end).

💡 Consider the smallest grid possible.

💡 If the only cell is not an obstacle, path count is 1.

💡 Return 0 only if the single cell is an obstacle.

Why it failed: Returned 0 for single cell with no obstacle; fix by returning 1 if obstacleGrid[0][0] == 0.

✓ Correctly returns 1 for single cell with no obstacle.

t2_02edge

Input{"obstacleGrid":[[1]]}

Expected0

⏱ Performance - must finish in 2000ms

Single cell grid with obstacle means no valid path.

💡 Check if start cell is blocked.

💡 If obstacleGrid[0][0] == 1, return 0 immediately.

💡 No paths exist if start or end is blocked.

Why it failed: Returned 1 for single cell with obstacle; fix by returning 0 if obstacleGrid[0][0] == 1.

✓ Correctly returns 0 when single cell is blocked.

t2_03edge

Input{"obstacleGrid":[[1,0],[0,0]]}

Expected0

⏱ Performance - must finish in 2000ms

Start cell is blocked, so no paths exist.

💡 Check if the starting cell is an obstacle.

💡 If obstacleGrid[0][0] == 1, return 0 immediately.

💡 No paths possible if start is blocked.

Why it failed: Returned non-zero paths despite start cell blocked; fix by checking obstacleGrid[0][0] before dp.

✓ Correctly returns 0 when start cell is blocked.

t3_01corner

Input{"obstacleGrid":[[0,0,0],[1,1,0],[0,0,0]]}

Expected1

⏱ Performance - must finish in 2000ms

Only one path exists going right->right->down->down avoiding obstacles blocking the middle row start.

💡 Beware of greedy approaches that pick paths without considering obstacles blocking entire rows.

💡 Use full DP to accumulate paths from top-left to bottom-right.

💡 Ensure dp sums paths from top and left cells only if those cells are reachable.

Why it failed: Greedy approach failed by ignoring blocked middle row; fix by using DP to accumulate all valid paths.

✓ DP correctly counts paths despite blocked rows.

t3_02corner

Input{"obstacleGrid":[[0,0,0,0],[0,1,1,0],[0,0,0,0]]}

Expected2

⏱ Performance - must finish in 2000ms

Multiple paths exist avoiding obstacles in middle row; counting all valid paths is required.

💡 Don't confuse 0/1 knapsack style problems with path counting.

💡 Count all possible paths using DP, not just one path.

💡 Sum dp[i-1][j] and dp[i][j-1] only if those cells are not obstacles.

Why it failed: Mistakenly returned 1 path due to greedy or 0/1 confusion; fix by summing all valid paths in DP.

✓ Correctly counts all unique paths avoiding obstacles.

t3_03corner

Input{"obstacleGrid":[[0,0,0],[0,1,0],[0,0,1]]}

Expected0

⏱ Performance - must finish in 2000ms

End cell is blocked, so no valid paths exist.

💡 Check if the ending cell is an obstacle.

💡 If obstacleGrid[m-1][n-1] == 1, return 0 immediately.

💡 No paths possible if end is blocked.

Why it failed: Returned non-zero paths despite end cell blocked; fix by checking obstacleGrid[m-1][n-1] before DP.

✓ Correctly returns 0 when end cell is blocked.

t4_01performance

Input{"obstacleGrid":[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large 10x100 grid with no obstacles; n=10, m=100, O(m*n) DP must complete within 2s.

💡 Use bottom-up DP with O(m*n) time complexity.

💡 Avoid recursion or exponential brute force approaches.

💡 Use space optimization if needed to reduce memory.

Why it failed: TLE due to exponential brute force recursion; fix by implementing O(m*n) DP solution.

✓ Efficient DP solution runs within time limits.

Practice

1. Consider the following code for minimum score triangulation of a polygon with vertex values [1, 3, 1, 4]. What is the final returned value?

easy

A. 7

B. 12

C. 10

D. 13

Solution

1. Step 1: Trace dp for length=3 (triangles)

   For i=0,j=2: dp[0][2] = 1*3*1=3; for i=1,j=3: dp[1][3] = 3*1*4=12

2. Step 2: Trace dp for length=4 (whole polygon)

   For i=0,j=3, k=1: cost=dp[0][1]+dp[1][3]+1*3*4=0+12+12=24; k=2: cost=dp[0][2]+dp[2][3]+1*1*4=3+0+4=7; dp[0][3]=7

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimal triangulation cost is 7, not 9 or higher [OK]

Hint: Check all k splits for minimal dp[i][j] cost [OK]

Common Mistakes:

• Off-by-one in loops
• Ignoring dp initialization
• Wrong triangle cost calculation

2. You are given an array of piles of stones. Two players alternately take stones from either end of the array, aiming to maximize their total stones. Both players play optimally. Which algorithmic approach guarantees finding the maximum difference in stones the first player can achieve over the second?

easy

A. Dynamic programming using interval-based state representation

B. Sorting piles and picking stones from the largest piles first

C. Simple recursion without memoization

D. Greedy approach picking the largest pile at each turn

Solution

1. Step 1: Understand the problem structure

   The problem involves two players picking from ends of an array, which naturally forms intervals that shrink over time.

2. Step 2: Identify the suitable algorithmic pattern

   Dynamic programming with intervals captures the state (i, j) representing the current subarray, allowing optimal substructure and overlapping subproblems to be exploited.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Interval DP is the classic approach for two-player games on arrays [OK]

Hint: Two-player games on arrays -> interval DP [OK]

Common Mistakes:

• Thinking greedy works because largest pile seems best
• Using recursion without memoization causes TLE

3. You are given a triangular array of numbers where each element can only move to one of the two adjacent numbers in the row below. The goal is to find the minimum sum path from the top to the bottom. Which algorithmic approach guarantees an optimal solution efficiently?

easy

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

B. Divide and conquer by splitting the triangle into two halves and solving independently

C. Pure brute force recursion exploring all paths without memoization

D. Dynamic Programming using bottom-up tabulation to build minimum path sums

Solution

1. Step 1: Understand problem constraints and properties

   The problem requires finding a minimum path sum with overlapping subproblems and optimal substructure, which suits dynamic programming.

2. Step 2: Identify suitable algorithm

   Bottom-up DP tabulation efficiently computes minimum sums from the bottom row up, avoiding recomputation and ensuring optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP tabulation solves overlapping subproblems efficiently [OK]

Hint: DP bottom-up tabulation ensures optimal substructure [OK]

Common Mistakes:

• Assuming greedy choice is always optimal
• Using brute force recursion without memoization
• Trying to split triangle independently ignoring dependencies

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 problem is modified so that the matrix can contain '1's and '0's, but you want to find the largest square containing only '1's where you are allowed to flip at most one '0' inside the square to '1'. Which of the following approaches correctly adapts the DP solution to handle this variant efficiently?

hard

A. Maintain two DP arrays: one for squares with zero flips and one for squares with one flip allowed, updating both simultaneously

B. Use the original DP but treat all '0's as '1's to allow flipping implicitly

C. Run the original DP multiple times, each time flipping a different '0' to '1' and taking the max result

D. Use a greedy approach to find the largest square ignoring zeros, then check if flipping one zero inside is possible

Solution

1. Step 1: Understand the variant

   Allowing one flip means tracking squares formed with zero or one zero flipped inside.

2. Step 2: Adapt DP states

   Maintain two DP states per cell: max square size without flips and with one flip used, updating both based on neighbors.

3. Step 3: Reject naive approaches

   Original DP ignores flips; multiple runs are inefficient; greedy ignores DP dependencies.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two DP arrays track flip states efficiently [OK]

Hint: Track DP states with and without flips [OK]

Common Mistakes:

• Ignoring flip state in DP
• Trying multiple brute force runs
• Using greedy without DP