Neetcode - Unique Paths

Don’t fear what you don’t know — it’s your next opportunity to grow.

This problem asks us to find the total number of possible paths from the starting point (0, 0) to the target position (m-1, n-1). The most straightforward approach is to use recursion to explore all possible paths and count those that successfully reach the goal. The routes typically follow this pattern:

(0,0, "")
├── (0,1, "R")
│ ├── (0,2, "RR")
│ │ ├── (1,2, "RRD")
│ │ │ └── (2,2, "RRDD") ← goal, add "RRDD"
│ │ └── (0,3, "RRR") [out of bounds, stop]
│ └── (1,1, "RD")
│ ├── (1,2, "RDR")
│ │ └── (2,2, "RDRD") ← goal, add "RDRD"
│ └── (2,1, "RDD")
│ └── (2,2, "RDDR") ← goal, add "RDDR"
└── (1,0, "D")
├── (1,1, "DR")
│ ├── (1,2, "DRR")
│ │ └── (2,2, "DRRD") ← goal, add "DRRD"
│ └── (2,1, "DRD")
│ └── (2,2, "DRDD") ← goal, add "DRDD"
└── (2,0, "DD")
├── (2,1, "DDR")
│ └── (2,2, "DDRR") ← goal, add "DDRR"
└── (3,0, "DDD") [out of bounds, stop]

Let's see how the code is implemented using DFS.

class Solution {
public:
    int uniquePaths(int m, int n) {
        set<string> visited;

        dfs(0, 0, "", m, n, visited);
        return visited.size();
    }

    void dfs(int row, int col, string route, int m, int n, set<string>& visited) {
        if (row >= m || col >= n) return;

        if (row == m - 1 && col == n - 1) {
            visited.insert(route);
            return;
        }
 
        dfs(row + 1, col, route + "D", m, n, visited);
        dfs(row, col + 1, route + "R", m, n, visited);
    }
};

In this code snippet, we use a set to track unique routes; if a route is not yet recorded, we continue traversing by moving either right or down. Next, let's explore how to solve the problem more efficiently using a dynamic programming (DP) approach.

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));

        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];        
    }
};

This approach demonstrates how succinctly we can solve the problem by calculating the number of paths to each reachable position.

For example, in a 2×2 grid, to reach the position (1, 1), you can arrive from either (0, 1) or (1, 0). Each of those two positions has only one path leading to them, so the total number of paths to (1, 1) is the sum of paths from both, which is two.

You can further explore and deduce this recursive relationship by analyzing grids of size 2×2 and 3×3 to identify the underlying pattern.