57. Unique Paths

MediumDynamic Programming Math Matrix

A robot stands in the top-left cell of an m × n grid (m rows, n columns). It can only move one cell right or one cell down at a time.

Return the number of distinct routes that take the robot to the bottom-right cell.

Example 1

Input: m = 3, n = 3
Output: 6

Explanation: Every route makes 2 right moves and 2 down moves, and there are 6 ways to order them (RRDD, RDRD, RDDR, DRRD, DRDR, DDRR).

Example 2

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

Explanation: RRD, RDR and DRR.

Example 3

Input: m = 1, n = 5
Output: 1

Explanation: With a single row the only route is straight to the right.

Constraints

1 <= m, n <= 100
The answer is at most 2 * 10^9

Follow-up: Some cells are now blocked by obstacles. How does the recurrence change?

💡 Hint 1

The only ways into cell (r, c) are from the cell above it and from the cell to its left.

💡 Hint 2

So paths[r][c] = paths[r - 1][c] + paths[r][c - 1], with every cell in the first row and first column equal to 1.

💡 Hint 3

You only need one row of the table at a time. (There is also a closed form: choose which of the m + n - 2 moves are the m - 1 down moves.)

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Count routes cell by cell. A cell in the first row or first column has exactly one route; any other cell is reached either from above or from the left, so its count is the sum of those two. Keep a single array row of length n initialised to 1s; for each following row, update left to right with row[c] += row[c - 1] (the old row[c] is the value from above, row[c - 1] is already the value to the left). The last entry is the answer. Equivalently the answer is the binomial coefficient C(m + n - 2, m - 1).

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

function uniquePaths(m, n) {
  const row = new Array(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) row[c] += row[c - 1];
  }
  return row[n - 1];
}

class Solution {
    public int uniquePaths(int m, int n) {
        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];
    }
}

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
function uniquePaths(m, n) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit