Unique Paths

Loading...LeetCode

Problem

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[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 * 109.

Example 1:

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

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Pseudocode

- dfs to find all paths, use memo to reduce recursion if function has been there
    - dfs will return all unique paths

Solution

var uniquePaths = function (m, n) {
  let map = [];

  for (let i = 0; i < m; i++) {
    map.push(new Array(n).fill(0));
  }

  return walk(0, 0, m, n, map, 0);
};

function walk(x, y, m, n, map, count) {
  // base condition
  if (x >= m || y >= n) {
    return 0;
  }

  // we've been here before, just add
  if (map[x][y] !== 0) {
    return map[x][y];
  }

  // if arrived at target return 1
  if (x === m - 1 && y === n - 1) {
    return 1;
  }

  // pre
  // recurse
  const down = walk(x + 1, y, m, n, map, count);
  const right = walk(x, y + 1, m, n, map, count);
  // post
  const sum = down + right;
  map[x][y] = sum;
  count += sum;
  return count;
}

Time and Space Complexity

Time

• What did the code do

• Total -

Space

• What did the code do

• Total -