Unique Paths II: Grid Paths with Obstacles

115k
0

An m x n grid contains open cells marked 0 and obstacles marked 1. A robot starts at the top-left cell and must reach the bottom-right cell.

Only right and down movements are allowed. Return the number of distinct paths containing only open cells.

Example 1

Input: grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: 2
Explanation: The valid move sequences are Right -> Right -> Down -> Down and Down -> Down -> Right -> Right.

Example 2

Input: grid = [[1]]
Output: 0
Explanation: The starting cell is blocked, so no path can begin.

Recursion

Every path reaching an open cell must arrive from directly above or directly left. The two final-move groups never overlap, so adding both counts gives the total for the cell. A boundary crossing or obstacle contributes no valid route.

Recursion applies the same smaller path-counting task at every position. The state solve(row, col) represents the number of valid paths from the start to (row, col). The public method begins at the destination because the destination state represents the complete grid journey, and recursive calls walk backward toward the start.

Algorithm

  • Define solve(row, col) as the number of valid paths from the start to a selected cell, so every recursive state has one clear meaning.

  • Return 0 after a negative row or column appears because a position outside the grid cannot belong to a valid route.

  • Return 0 for an obstacle because no path may enter a blocked cell or continue through a blocked state.

  • Return 1 at the open starting cell because staying at the start forms the single path prefix needed by later states.

  • Request the path counts from above and left because every legal final move into the selected cell comes from exactly one of the two positions.

  • Add both recursive answers because the final move separates all valid paths into two disjoint groups.

  • Start recursion at the bottom-right cell because the destination state contains the answer for the entire grid.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Counts valid paths ending at a selected cell.
int solve(int row, int col, vector<vector<int>>& grid) {
// Rejects positions outside the grid.
if (row < 0 || col < 0) {
return 0;
}
// Rejects paths entering an obstacle.
if (grid[row][col] == 1) {
return 0;
}
// Counts the open starting cell as one path.
if (row == 0 && col == 0) {
return 1;
}
// Counts paths arriving from the cell above.
int fromAbove = solve(row - 1, col, grid);
// Counts paths arriving from the cell on the left.
int fromLeft = solve(row, col - 1, grid);
// Adds disjoint final-move groups.
return fromAbove + fromLeft;
}
public:
// Returns the number of obstacle-free paths.
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
// Starts from the destination for the full grid.
return solve(rows - 1, cols - 1, grid);
}
};
// Driver code
int main() {
vector<vector<int>> grid = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
Solution obj;
cout << obj.uniquePathsWithObstacles(grid);
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2(M + N)), where M is the number of rows and N is the number of columns, because each recursive level can branch into at most two choices across a path of length up to M + N - 2.

Space Complexity: O(M + N), because the recursion stack can contain at most one active call for each row or column move along a path.

Memoization

Direct recursion reaches the same cell through many different move sequences. Every repeated call asks for the same path count, so recalculation adds avoidable work.

A 2D array named dp stores the answer for every state (row, col). A stored value is returned immediately during later visits. The recursive state and recurrence remain unchanged.

Algorithm

  • Fill a grid-shaped dp matrix with -1 so every untouched entry clearly marks an uncalculated path count.

  • Keep solve(row, col) identical to the recursive state so memoization changes only repeated work, not the path-count meaning.

  • Return 0 for a boundary crossing or obstacle because neither invalid state can finish a valid path prefix.

  • Return 1 at the open starting cell because every later count must grow from one valid starting prefix.

  • Reuse dp[row][col] whenever a stored answer exists because every visit to the same cell asks for the same path count.

  • Add the answers from above and left, then store the sum in dp[row][col] so later branches avoid recalculation.

  • Begin at the destination and return the saved destination count because the destination state represents the complete problem.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Counts paths and stores completed states.
int solve(int row, int col, vector<vector<int>>& grid,
vector<vector<int>>& dp) {
// Rejects positions outside the grid.
if (row < 0 || col < 0) {
return 0;
}
// Rejects paths entering an obstacle.
if (grid[row][col] == 1) {
return 0;
}
// Counts the open starting cell as one path.
if (row == 0 && col == 0) {
return 1;
}
// Reuses a previously calculated path count.
if (dp[row][col] != -1) {
return dp[row][col];
}
// Counts paths arriving from the cell above.
int fromAbove = solve(row - 1, col, grid, dp);
// Counts paths arriving from the cell on the left.
int fromLeft = solve(row, col - 1, grid, dp);
// Stores the sum to avoid repeated work.
dp[row][col] = fromAbove + fromLeft;
return dp[row][col];
}
public:
// Returns the number of obstacle-free paths.
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
vector<vector<int>> dp(rows, vector<int>(cols, -1));
// Starts from the destination for the full grid.
return solve(rows - 1, cols - 1, grid, dp);
}
};
// Driver code
int main() {
vector<vector<int>> grid = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
Solution obj;
cout << obj.uniquePathsWithObstacles(grid);
return 0;
}

Complexity Analysis

Time Complexity: O(M × N), where M is the number of rows and N is the number of columns, because each grid state is computed at most once with constant work.

Space Complexity: O(M × N), because the dp matrix stores M × N values, while the recursion stack adds at most O(M + N) space.

Tabulation

Memoization still depends on recursive calls. Tabulation evaluates the same states directly in row-major order, removing recursion while preserving the recurrence.

For an open cell, the value above has already been calculated in the previous row, and the value left has already been calculated in the current row. An obstacle receives 0, preventing blocked routes from contributing to later cells.

Algorithm

  • Initialize a grid-shaped dp matrix with 0 so blocked cells and unavailable predecessors naturally contribute no paths.

  • Process cells from top to bottom and left to right because every required state above or left must be ready before use.

  • Keep 0 at every obstacle because blocked cells cannot receive a path or pass a count to a later cell.

  • Store 1 at the open starting cell because one valid path prefix begins before any movement occurs.

  • Read the value above only below the top edge, using 0 on the edge because no valid predecessor exists outside the grid.

  • Read the value left only beyond the first column, again using 0 because no path can enter from outside the grid.

  • Add both predecessor counts for every other open cell and return dp[m - 1][n - 1] because the destination entry collects every valid route.

Dry Run

Unique Path II Tabulation

Unique Path II Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the path count through tabulation.
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
vector<vector<int>> dp(rows, vector<int>(cols, 0));
// Processes cells after predecessor states are ready.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// Keeps every blocked state unreachable.
if (grid[row][col] == 1) {
dp[row][col] = 0;
continue;
}
// Initializes the only path at the starting cell.
if (row == 0 && col == 0) {
dp[row][col] = 1;
continue;
}
int fromAbove = 0;
int fromLeft = 0;
// Reads the predecessor above only inside the grid.
if (row > 0) {
fromAbove = dp[row - 1][col];
}
// Reads the predecessor left only inside the grid.
if (col > 0) {
fromLeft = dp[row][col - 1];
}
// Adds both valid predecessor groups.
dp[row][col] = fromAbove + fromLeft;
}
}
return dp[rows - 1][cols - 1];
}
};
// Driver code
int main() {
vector<vector<int>> grid = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
Solution obj;
cout << obj.uniquePathsWithObstacles(grid);
return 0;
}

Complexity Analysis

Time Complexity: O(M × N), where M is the number of rows and N is the number of columns, because each grid cell is processed once with constant work.

Space Complexity: O(M × N), because the dp matrix stores one path count for every grid cell and no recursion stack is used.

Space Optimization

Tabulation uses only the value above from the previous row and the value left from the current row. Older rows never contribute again, so a full matrix is unnecessary.

A one-dimensional dp array stores path counts for the active row. Before an update, dp[col] represents the value above, while dp[col - 1] represents the value left. The predecessor sum forms current, and assigning current to dp[col] shifts the column state to the active row.

Algorithm

  • Initialize a one-dimensional dp array with 0 so every column starts unreachable before row processing begins.

  • Process each row from left to right because dp[col] must still hold the value above while dp[col - 1] already holds the current-row value from left.

  • Reset dp[col] to 0 at an obstacle because no blocked state may survive and contribute to later cells.

  • Store 1 at the open starting cell because the first path prefix exists before any move is taken.

  • Read dp[col] as fromAbove and the preceding entry as fromLeft because the one-dimensional array preserves both required predecessor states.

  • Calculate current by adding both predecessor counts because every path reaches the active cell from exactly one direction.

  • Shift current into dp[col] and return the last entry because completed updates leave the destination count at the final column.

Dry Run

Unique Path II Space Optimization

Unique Path II Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the number of paths with one-dimensional storage.
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
vector<int> dp(cols, 0);
// Processes rows while reusing the same column states.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// Clears every blocked column state.
if (grid[row][col] == 1) {
dp[col] = 0;
continue;
}
// Initializes the only path at the starting cell.
if (row == 0 && col == 0) {
dp[col] = 1;
continue;
}
int fromAbove = dp[col];
int fromLeft = 0;
// Reads the active-row value from the left.
if (col > 0) {
fromLeft = dp[col - 1];
}
// Calculates current from above and left.
int current = fromAbove + fromLeft;
// Shifts the column state to the active row.
dp[col] = current;
}
}
return dp[cols - 1];
}
};
// Driver code
int main() {
vector<vector<int>> grid = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
Solution obj;
cout << obj.uniquePathsWithObstacles(grid);
return 0;
}

Complexity Analysis

Time Complexity: O(M × N), where M is the number of rows and N is the number of columns, because each grid cell is processed once with constant work.

Space Complexity: O(N), because one path count is stored for each column while values from older rows are discarded.

Interview follow-up Questions

The answer becomes 0. A blocked starting cell prevents any path from beginning, while a blocked destination prevents any path from finishing.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals targe...

55.1k
Comments0