Unique Paths

Problem Description

There is a robot on an m × n grid. The robot is initially located at the top-left corner (0, 0). The robot tries to move to the bottom-right corner (m - 1, n - 1). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10⁹.

Examples

Constraints

• 1 ≤ m, n ≤ 100

Combining Incoming Paths from Top and Left

Since the robot can only move down or right, any cell (r, c) can only be entered from the cell above it (r - 1, c) or the cell to its left (r, c - 1).

Therefore, the number of unique paths to reach cell (r, c) is the sum of the paths to reach its top neighbor and its left neighbor: paths(r, c) = paths(r - 1, c) + paths(r, c - 1).

This recurrence relation allows bottom-up 2D tabulation. The top row and left column have only 1 unique path (moving straight right or straight down). For other cells, we calculate values sequentially. Because computing a new row only requires values from the current row and the row above it, we can optimize space to O(n) by using a single 1D array representing the active row.

Solution 1: Dynamic Programming (1D Array Space Optimization)

Maintain a single 1D array row of size n initialized to 1. For each subsequent row, update the values iteratively: row[c] = row[c] + row[c - 1].

import java.util.Arrays;

class Solution {
    public int uniquePaths(int m, int n) {
        int[] row = new int[n];
        Arrays.fill(row, 1); // base case: top row initialized to 1

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                // row[c] is the cell above; row[c-1] is the cell to the left
                row[c] = row[c] + row[c - 1];
            }
        }
        return row[n - 1];
    }
}

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n  # base case: top row initialized to 1

        for r in range(1, m):
            for c in range(1, n):
                # row[c] is the cell above; row[c-1] is the cell to the left
                row[c] = row[c] + row[c - 1]

        return row[n - 1]

#include <vector>

class Solution {
public:
    int uniquePaths(int m, int n) {
        std::vector<int> row(n, 1); // base case: top row initialized to 1

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                // row[c] is the cell above; row[c-1] is the cell to the left
                row[c] = row[c] + row[c - 1];
            }
        }
        return row[n - 1];
    }
};

Complexity Analysis:

• Time Complexity: O(m * n) since we evaluate all cell positions once.
• Space Complexity: O(n) to store the 1D state array.

Where it breaks: Nothing breaks for standard ranges. If m and n are extremely large, using the combinatorics formula below is faster and uses O(1) space.

Solution 2: Combinatorics (O(1) Space)

The robot must make exactly m - 1 down steps and n - 1 right steps, regardless of the path. The total steps is (m - 1) + (n - 1) = m + n - 2. The number of unique paths is the number of ways to choose the down steps from the total steps, which is represented by the combination formula: (m + n - 2) Choose (m - 1).

class Solution {
    public int uniquePaths(int m, int n) {
        long result = 1;
        int totalMoves = m + n - 2;
        int downMoves = Math.min(m - 1, n - 1);

        for (int i = 1; i <= downMoves; i++) {
            result = result * (totalMoves - downMoves + i) / i;
        }
        return (int) result;
    }
}

import math


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # combination formula: (m + n - 2) Choose (m - 1)
        return math.comb(m + n - 2, m - 1)

#include <algorithm>

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long result = 1;
        int totalMoves = m + n - 2;
        int downMoves = std::min(m - 1, n - 1);

        for (int i = 1; i <= downMoves; i++) {
            result = result * (totalMoves - downMoves + i) / i;
        }
        return (int)result;
    }
};

Complexity Analysis:

• Time Complexity: O(min(m, n)) to compute the combination factors.
• Space Complexity: O(1) auxiliary space.

Where it breaks: During calculation of the combination factor multiplication result * (totalMoves - downMoves + i), values can overflow standard 64-bit integers if not handled carefully with divisions inside the loop. The Math.min(m - 1, n - 1) boundary selection helps contain intermediate values.

Common Mistakes

• Not handling the m == 1 or n == 1 cases. In a single-column or single-row grid, the robot has only 1 path (straight down or straight right). Both solutions handle this correctly (loops do not execute, returning 1).
• Using a full 2D array when 1D array space is requested. Reducing space from O(m * n) to O(n) is a standard interview optimization.
• Integer overflow during combinations calculations. Ensure you divide early or use long types to protect intermediate multiplications.

Frequently Asked Questions

Why does row[c] = row[c] + row[c - 1] work in 1D space? Before updating, row[c] contains the value from the previous row (the top neighbor). row[c - 1] contains the already updated value for the current row (the left neighbor). Adding them updates row[c] correctly.

How does this change if there are obstacles in the grid? If there are obstacles (Unique Paths II), you set row[c] = 0 whenever you encounter an obstacle, and continue the sum propagation for valid cells.

What does this problem test in interviews? It tests your ability to translate coordinate grid movements into mathematical recurrence relations, and optimize 2D space allocation to 1D.

← All Problems