62. Unique Paths

NeetCode: Unique Paths · LeetCode: 62. Unique Paths · Difficulty: Medium

A robot starts in the top-left corner of an m x n grid and wants to reach the bottom-right corner. It can only move right or down. Return the number of distinct paths.

Example

Input:  m = 3, n = 7    Output: 28
Input:  m = 3, n = 2    Output: 3

Brute force: plain recursion

The number of ways to reach a cell is the number of ways to go right from it plus the number of ways to go down from it. Count the moves still needed in each direction: with rows moves down and cols moves right remaining, paths(rows, cols) = paths(rows - 1, cols) + paths(rows, cols - 1), and once either count hits zero only one straight line is left. The recursion tree branches twice at almost every step and recomputes the same cells over and over, so it takes exponential time.

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) return 0;
        if (m == 1 || n == 1) return 1;
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.uniquePaths(3, 7));
        System.out.println(s.uniquePaths(3, 2));
        System.out.println(s.uniquePaths(1, 1));
    }
}

28
3
1

Time: O(2^(m+n)). Space: O(m + n) for the recursion stack.

Better: 2D table

There are only m * n distinct subproblems, so store each once. dp[r][c] is the number of ways to reach cell (r, c) from the start; the first row and first column are all 1 (one straight line), and every other cell is dp[r-1][c] + dp[r][c-1].

import java.util.Arrays;

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) return 0;
        int[][] dp = new int[m][n];
        for (int[] row : dp) Arrays.fill(row, 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];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.uniquePaths(3, 7));
        System.out.println(s.uniquePaths(3, 2));
        System.out.println(s.uniquePaths(1, 1));
    }
}

28
3
1

Time: O(m · n). Space: O(m · n).

Optimal: one rolling row

Row r only needs row r - 1 (the cell above) and the cell to its own left. Keep a single row and update it in place: before the update row[c] still holds the value from above, and row[c - 1] has already been updated, so row[c] += row[c - 1] is exactly the recurrence.

import java.util.Arrays;

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) return 0;
        int[] row = new int[n];
        Arrays.fill(row, 1);
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                row[c] += row[c - 1];
            }
        }
        return row[n - 1];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.uniquePaths(3, 7));
        System.out.println(s.uniquePaths(3, 2));
        System.out.println(s.uniquePaths(1, 1));
    }
}

28
3
1

Time: O(m · n). Space: O(n).

A closed form also exists: every path is an arrangement of m - 1 downs and n - 1 rights, so the answer is the binomial coefficient C(m + n - 2, m - 1). The DP avoids the large intermediate products that computing the binomial directly can produce, which would overflow int (and eventually long) silently. LeetCode guarantees the answer is at most 2 * 10^9, which fits in a 32-bit int, so the DP sums never overflow.