02. Unique Paths in a Grid

✅ GFG solution to the Unique Paths in a Grid problem: count ways to traverse a grid with obstacles using optimized DP.

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given a 2D list grid[][] of size n × m consisting of values 0 and 1.

A value of 0 means that you can enter that cell.
A value of 1 implies that entry to that cell is not allowed (an obstacle).

You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner (n, m) by moving only right or down at each step. Your task is to calculate the total number of ways to reach the target.

Note: The first (1, 1) and last (n, m) cells of the grid can also be 1. It is guaranteed that the total number of ways will fit within a 32-bit integer.

📘 Examples

Example 1

Input: n = 3, m = 3,
grid = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
]

Output: 2
Explanation:
There are two ways to reach the bottom-right corner:
1. Right → Right → Down → Down
2. Down → Down → Right → Right

Example 2

Input: n = 1, m = 3,
grid = [[1, 0, 1]]

Output: 0
Explanation:
The start cell (1,1) is blocked by an obstacle (value = 1), so no path exists.

🔒 Constraints

$1 \le n \times m \le 10^6$
Each grid[i][j] is either 0 or 1.
The result will fit in a 32-bit integer.

✅ My Approach

We use dynamic programming with a 1D rolling array to count the number of ways to reach each cell, optimizing space.

💡 Idea:

Let dp[j] represent the number of ways to reach cell (i, j) in the current row i.
We iterate row by row. For each cell:
1. If grid[i][j] == 1 (obstacle), set dp[j] = 0 (no way).
2. Else, if j > 0, add dp[j - 1] (ways from the left) to dp[j] (which already holds ways from above).
Initialize dp[0] as 1 if grid[0][0] == 0, else 0.

This effectively uses the previous row’s dp[j] values (ways from above) and the current row’s left neighbor dp[j - 1] (ways from left).

⚙️ Algorithm Steps:

Let r = n, c = m. Create a 1D array dp of size c, initialized to all zeros.
If grid[0][0] == 0, set dp[0] = 1; otherwise dp[0] = 0.
For each row i from 0 to r - 1:
- For each column j from 0 to c - 1:
  1. If grid[i][j] == 1:
    dp[j] = 0 (no paths through an obstacle).
  2. Else if j > 0:
    dp[j] += dp[j - 1] (add ways from the left).
At the end, dp[c - 1] holds the number of ways to reach (r - 1, c - 1).

📝 Time and Auxiliary Space Complexity

Expected Time Complexity: O(n × m), as we process each of the $n \times m$ cells exactly once.
Expected Auxiliary Space Complexity: O(m), since we use a single array of size m for DP.

🧑‍💻 Code (C++)

class Solution {
  public:
    int uniquePaths(vector<vector<int>> &grid) {
        int r = grid.size(), c = grid[0].size();
        vector<int> dp(c);
        dp[0] = grid[0][0] == 0;
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                if (grid[i][j]) dp[j] = 0;
                else if (j) dp[j] += dp[j - 1];
        return dp[c - 1];
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ 2D Dynamic Programming (Tabulation)

We use a 2D dp array where dp[i][j] denotes number of ways to reach cell (i,j).

💡 Algorithm Steps:

Initialize a 2D dp array of size r × c with zeros.
If grid[0][0] is not blocked, set dp[0][0] = 1.
For the first row and first column, set dp[i][0] and dp[0][j] to 1 if no obstacles block the path; else 0.
For each cell (i, j), if no obstacle, set dp[i][j] = dp[i-1][j] + dp[i][j-1].
Return dp[r-1][c-1].

class Solution {
  public:
    int uniquePaths(vector<vector<int>>& grid) {
        int r = grid.size(), c = grid[0].size();
        vector<vector<int>> dp(r, vector<int>(c, 0));
        if (grid[0][0]) return 0;
        dp[0][0] = 1;
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                if (!grid[i][j]) {
                    if (i) dp[i][j] += dp[i - 1][j];
                    if (j) dp[i][j] += dp[i][j - 1];
                }
        return dp[r - 1][c - 1];
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(m × n)
Auxiliary Space: 💾 O(m × n)

✅ Why This Approach?

Simple and straightforward.
Useful when readability is more important than space optimization.

📊 3️⃣ In-Place Grid Modification

Instead of using extra arrays, overwrite grid itself to store the count of paths.

💡 Algorithm Steps:

If grid[0][0] == 1, return 0 immediately.
Set grid[0][0] = 1 to represent path count.
Update first row and column to carry forward path counts until obstacles are found.
For other cells, update grid[i][j] = grid[i-1][j] + grid[i][j-1] if not blocked; else 0.
Return grid[r-1][c-1].

class Solution {
  public:
    int uniquePaths(vector<vector<int>>& grid) {
        int r = grid.size(), c = grid[0].size();
        if (grid[0][0] == 1) return 0;
        grid[0][0] = 1;
        for (int j = 1; j < c; ++j)
            grid[0][j] = (grid[0][j] == 1 ? 0 : grid[0][j - 1]);
        for (int i = 1; i < r; ++i)
            grid[i][0] = (grid[i][0] == 1 ? 0 : grid[i - 1][0]);
        for (int i = 1; i < r; ++i)
            for (int j = 1; j < c; ++j)
                grid[i][j] = (grid[i][j] == 1 ? 0 : grid[i - 1][j] + grid[i][j - 1]);
        return grid[r - 1][c - 1];
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(m × n)
Auxiliary Space: 💾 O(1)

✅ Why This Approach?

No extra space is needed.
Best when modifying the input grid is allowed.

📊 4️⃣ Top-Down Recursion with Memoization

Use recursion to explore paths from (0,0) to (r-1,c-1) and store results in a memo table to avoid recomputation.

💡 Algorithm Steps:

Use a 2D memo array initialized with -1.
Define recursive dfs(i, j) that:
- Returns 0 if out of bounds or on an obstacle.
- Returns 1 if at the start (0,0).
- Otherwise returns sum of dfs(i-1, j) and dfs(i, j-1).
Cache results to avoid recomputation.
Call dfs(r-1, c-1).

class Solution {
  public:
    int r, c;
    vector<vector<int>> memo;
    vector<vector<int>> *g;

    int dfs(int i, int j) {
        if (i < 0 || j < 0 || (*g)[i][j] == 1) return 0;
        if (i == 0 && j == 0) return 1;
        if (memo[i][j] != -1) return memo[i][j];
        int up = dfs(i - 1, j);
        int left = dfs(i, j - 1);
        return memo[i][j] = up + left;
    }

    int uniquePaths(vector<vector<int>>& grid) {
        g = &grid;
        r = grid.size(); c = grid[0].size();
        memo.assign(r, vector<int>(c, -1));
        return dfs(r - 1, c - 1);
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(m × n)
Auxiliary Space: O(m × n) memo + O(m+n) recursion stack

✅ Why This Approach?

Good for understanding recursion and memoization.
Avoids unnecessary computation on blocked paths.

🆚 🔍 Comparison of Approaches

🚀 Approach

⏱️ Time Complexity

💾 Space Complexity

✅ Pros

⚠️ Cons

🔢 1D DP (Rolling Array)

🟢 O(n × m)

🟢 O(m)

Space-optimized, easy implementation

Slightly less intuitive than 2D DP

📊 2D DP (Tabulation)

🟢 O(n × m)

🟡 O(n × m)

Very intuitive, straightforward

High space usage for large grids

🏗️ In-Place Grid Modification

🟢 O(n × m)

🟢 O(1)

No extra space needed

Modifies input grid (side effect)

🔄 Top-Down Memoized Recursion

🟢 O(n × m)

🔴 O(n × m) + recursion

Clear recursion logic with memoization

Extra stack space, overhead of recursion

🏆 Best Choice by Scenario

🎯 Scenario

🥇 Recommended Approach

🏁 Memory-constrained, large grids

🥇 1D DP Rolling Array

💻 Prioritize clarity and debugging

🥈 2D DP Tabulation

⚡ Strict space limitation and can modify input grid

🥉 In-Place Grid Modification

🔍 Learning recursion and memoization

🎖️ Top-Down Memoized Recursion

🧑‍💻 Code (Java)

class Solution {
    public int uniquePaths(int[][] grid) {
        int r = grid.length, c = grid[0].length;
        int[] dp = new int[c];
        dp[0] = grid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                if (grid[i][j] == 1) dp[j] = 0;
                else if (j > 0) dp[j] += dp[j - 1];
        return dp[c - 1];
    }
}

🐍 Code (Python)

class Solution:
    def uniquePaths(self, grid):
        r, c = len(grid), len(grid[0])
        dp = [0] * c
        dp[0] = 1 if grid[0][0] == 0 else 0
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 1:
                    dp[j] = 0
                elif j > 0:
                    dp[j] += dp[j - 1]
        return dp[-1]

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

Previous01. Count pairs Sum in matrices Next03. Substrings with K Distinct

Last updated 6 months ago

hashtag🧩 Problem Description

hashtag📘 Examples

hashtagExample 1

hashtagExample 2

hashtag🔒 Constraints

hashtag✅ My Approach

hashtag💡 Idea:

hashtag⚙️ Algorithm Steps:

hashtag📝 Time and Auxiliary Space Complexity

hashtag🧑‍💻 Code (C++)

hashtag📊 2️⃣ 2D Dynamic Programming (Tabulation)

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 3️⃣ In-Place Grid Modification

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Top-Down Recursion with Memoization

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag🆚 🔍 Comparison of Approaches

hashtag🏆 Best Choice by Scenario

hashtag🧑‍💻 Code (Java)

hashtag🐍 Code (Python)

hashtag🧠 Contribution and Support

hashtag📍Visitor Count

🧩 Problem Description

📘 Examples

Example 1

Example 2

🔒 Constraints

✅ My Approach

💡 Idea:

⚙️ Algorithm Steps:

📝 Time and Auxiliary Space Complexity

🧑‍💻 Code (C++)

📊 2️⃣ 2D Dynamic Programming (Tabulation)

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 3️⃣ In-Place Grid Modification

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Top-Down Recursion with Memoization

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

🆚 🔍 Comparison of Approaches

🏆 Best Choice by Scenario

🧑‍💻 Code (Java)

🐍 Code (Python)

🧠 Contribution and Support

📍Visitor Count