Difficulty: Medium · LeetCode 62

Problem

Robot at (0,0) in m x n grid wants to move to (m-1, n-1). Can only move down or right. Return total unique paths.

Understanding the problem

To reach cell (r, c), you can arrive from top (r-1, c) or left (r, c-1). Thus dp[r][c] = dp[r-1][c] + dp[r][c-1].

Intuition

Fill 2D grid bottom-up or optimize space to 1D row array of size n.

Approach

Initialize dp = [1] * n.
Loop m-1 times: for c from 1 to n-1, dp[c] += dp[c-1].
Return dp[-1].

Naive Solution — Recursion

At every cell, recursively branch right and down until reaching bottom-right corner.

Python

class Solution:
    def uniquePaths(self, m, n):

        def dfs(r, c):
            if r == m - 1 and c == n - 1:
                return 1

            if r >= m or c >= n:
                return 0

            return (
                dfs(r + 1, c)
                +
                dfs(r, c + 1)
            )

        return dfs(0, 0)

C++

class Solution {
public:
    int uniquePaths(int m, int n) {
        return dfs(0, 0, m, n);
    }

private:
    int dfs(int r, int c, int m, int n) {
        if (r == m - 1 && c == n - 1) return 1;
        if (r >= m || c >= n) return 0;

        return dfs(r + 1, c, m, n) + dfs(r, c + 1, m, n);
    }
};

Java

class Solution {
    public int uniquePaths(int m, int n) {
        return dfs(0, 0, m, n);
    }

    private int dfs(int r, int c, int m, int n) {
        if (r == m - 1 && c == n - 1) return 1;
        if (r >= m || c >= n) return 0;

        return dfs(r + 1, c, m, n) + dfs(r, c + 1, m, n);
    }
}

JavaScript

var uniquePaths = function(m, n) {
    const dfs = (r, c) => {
        if (r === m - 1 && c === n - 1) return 1;
        if (r >= m || c >= n) return 0;

        return dfs(r + 1, c) + dfs(r, c + 1);
    };

    return dfs(0, 0);
};

Time: O(2^(m+n)) · Aux Space: O(m+n)

Optimized Code (Python 3)

Python

class Solution:
    def uniquePaths(self, m, n):

        dp = [[0] * n for _ in range(m)]

        for r in range(m):
            dp[r][0] = 1

        for c in range(n):
            dp[0][c] = 1

        for r in range(1, m):
            for c in range(1, n):
                dp[r][c] = (
                    dp[r - 1][c]
                    +
                    dp[r][c - 1]
                )

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

C++

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

        for (int r = 0; r < m; r++) dp[r][0] = 1;
        for (int c = 0; c < n; c++) dp[0][c] = 1;

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

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

Java

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for (int r = 0; r < m; r++) dp[r][0] = 1;
        for (int c = 0; c < n; c++) dp[0][c] = 1;

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

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

JavaScript

var uniquePaths = function(m, n) {
    const dp = Array.from({ length: m }, () => new Array(n).fill(0));

    for (let r = 0; r < m; r++) dp[r][0] = 1;
    for (let c = 0; c < n; c++) dp[0][c] = 1;

    for (let r = 1; r < m; r++) {
        for (let c = 1; c < n; c++) {
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }

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

Time: O(mn) · Space: O(n) (Space Optimized) / O(mn) (2D Grid)

Takeaway

Grid DP — Each cell transitions from top and left adjacent neighbors.