Unique Paths

MediumDynamic Programming Math Matrix

A warehouse floor is a grid of m rows and n columns. A delivery robot starts in the top-left cell and must reach the bottom-right cell, and because the aisles are one-way, it can only move one cell right or one cell down at a time.

Return the number of different routes the robot can take.

Example 1

Input: m = 3, n = 4
Output: 10

Explanation: Every route makes 2 down moves and 3 right moves, and there are 10 ways to order those five moves.

Example 2

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

Explanation: The robot moves right exactly once, and it can do so in any of the 4 rows.

Example 3

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

Explanation: In a single row, the only route goes straight to the right.

Constraints

m and n are each between 1 and 100.
In every test the number of routes is at most 2 · 10^9.

Follow-up: Some cells are now blocked by pallets the robot cannot enter. 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