DSA

Unique Paths - II

4 approaches incl. A. Recursive, B. Memoization, B. Tabulation, and more. Optimal — Time O(m * n), Space O(n).

August 8, 2026

DSA Dynamic Programming DP LeetCode Practice

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

Practice Link

Implementation#

A. Recursive Approach#

Same structure as Unique Paths I, with one additional rule: if the current cell contains an obstacle (obstacleGrid[i][j] == 1), return 0 immediately. The recursion sums paths from the cell above and the cell to the left, bottoming out at the top-left corner. Overlapping sub-problems cause exponential time.

cpp

class Solution {
public:

    int findUniquePaths(vector<vector<int>>& obstacleGrid, int i, int j)
    {
        if(i<0 || j<0)
            return 0;

        if(obstacleGrid[i][j] == 1)
            return 0;

        if(i==0 && j==0 && obstacleGrid[i][j]==0)
            return 1;
        

        return findUniquePaths(obstacleGrid, i-1, j) + findUniquePaths(obstacleGrid, i, j-1);
    }

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        return findUniquePaths(obstacleGrid, m-1, n-1);
    }
};

Time Limit Exceeded - Overlapping Cases

B. Memoization#

Cache memo[i][j] — the number of unique paths from (0, 0) to (i, j). Note: the obstacle check must come before the memo lookup to avoid caching a valid-path count for an obstacle cell. Each of the m × n non-obstacle cells is computed once, giving O(m*n) time.

cpp

class Solution {
public:

    int findUniquePaths(vector<vector<int>>& obstacleGrid, int i, int j, vector<vector<int>> &memo)
    {
        if(i<0 || j<0)
            return 0;

        if(memo[i][j]!= -1)
            return memo[i][j];

        if(obstacleGrid[i][j] == 1)
            return 0;

        if(i==0 && j==0 && obstacleGrid[i][j]==0)
            return 1;
        

        return memo[i][j] = findUniquePaths(obstacleGrid, i-1, j, memo) + findUniquePaths(obstacleGrid, i, j-1, memo);
    }

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

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

        return findUniquePaths(obstacleGrid, m-1, n-1, memo);
    }
};

Time Complexity - O(m * n)

Space Complexity - O((n-1)+(m-1)) + O(m * n)

C. Tabulation Solution#

Fill the DP table top-left to bottom-right. The first row and column are initialized by propagating dp[0][0] = 1 as long as there are no obstacles (an obstacle in the first row/column blocks all further cells in that line). Interior cells sum the top and left values, or are set to 0 for obstacles. The iterative fill removes the recursion stack.

cpp

class Solution {
public:

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        if(obstacleGrid[0][0]==1)
            return 0;

        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = 1;

        for(int i=1;i<m;i++)
            if(obstacleGrid[i][0] != 1)
                dp[i][0] = dp[i-1][0];

        for(int j=1;j<n;j++)
            if(obstacleGrid[0][j] != 1)
                dp[0][j] = dp[0][j-1];   

        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(obstacleGrid[i][j]==0)
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                else
                    dp[i][j] = 0;
            }
        }
        return dp[m-1][n-1];
    }
};

Time Complexity - O(m * n)

Space Complexity - O(m * n)

D. Space Optimized Tabulation#

Each row reads only from the previous row (prev) and the current row's left neighbor. We keep two 1D arrays (prev and curr), resetting curr at the start of each row and swapping at the end. Space drops from O(m*n) to O(n).

cpp

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        if(matrix[0][0]==1)
            return 0;

        vector<int> prev(n, 0), curr(n,0);
        prev[0] = 1;

        for(int j=1;j<n;j++)
            if(matrix[0][j] != 1)
               prev[j] = prev[j-1];

        for(int i=1;i<m;i++){
            fill(curr.begin(), curr.end(), 0);
            for(int j=0;j<n;j++){
                if(matrix[i][j] == 1)
                    curr[j] = 0;
                else if(j==0)
                    curr[j] = prev[j];
                else
                    curr[j] = prev[j] + curr[j-1];

            }
            prev = curr;
        }
        return prev[n-1];
    }
};

Time Complexity - O(m * n)

Space Complexity - O(n)

DSALongest Common Prefix5 approaches incl. Horizontal Scanning, Vertical Scanning, Binary Search, and more. Optimal — Time O(s log m), Space O(1).DSAMaximum Subarray SumCovers: Brute Force, Optimal. Optimal — Time O(n), Space O(1).DSAPalindromic SubstringCovers: Brute Force: generate all su…, Expansion on center, DP. Optimal — Time O(n<sup>2</sup>), Space O(n<sup>2</sup>).