Command Palette

Search for a command to run...

Hectal
Problem 29.2 · DP on GridsMedium

Unique Paths II

PatternGrid DP

What it teaches: Obstacles zero out cells, including along the first row and column.

Practise it on judges as “Unique Paths II”.

The problem

Same as Unique Paths, but cells with 1 are obstacles. Return the number of paths avoiding them.

Example 1

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2

Constraints

  • 1 ≤ m, n ≤ 100

Pattern clues in the wording

  • → Count paths with blocked cells

These clues point to Grid DP: Each cell's answer comes from the cells above and to the left; fill the grid row by row.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
2
2
obstacleGrid = [[0,1],[0,0]]
1
3
obstacleGrid = [[1]]
0

From slow to fast

Approaches

1. One-row DP with obstacles · O(m × n)
1

One-row DP with obstacles

Time O(m × n) Space O(n)

dp[0] = 1. For each cell: obstacle → dp[c] = 0; else if c > 0, dp[c] += dp[c − 1].

Approach 1
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int[] row : obstacleGrid)
            for (int c = 0; c < n; c++) {
                if (row[c] == 1) dp[c] = 0;
                else if (c > 0) dp[c] += dp[c - 1];
            }
        return dp[n - 1];
    }
}

Verdict: Handles edges naturally.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Obstacle at the start or end (0)
  • Obstacle in the first row blocks everything to its right

Mistakes people make

  • Setting the whole first row to 1 regardless of obstacles.

Interview

Follow-up questions

What if moves could also go left or up?