Unique Paths Problem

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Unique Paths

Examples

Example #1

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

Example #2

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

Algorithms

Backtracking

First thought that might came to mind is that we need to build a decision tree where D means moving down and R means moving right. For example in case of boars width = 3 and height = 2 we will have the following decision tree:

  1.                 START
  2.                 /   \
  3.                D     R
  4.              /     /   \
  5.            R      D      R
  6.          /      /         \
  7.         R      R            D
  9.        END    END          END

We can see three unique branches here that is the answer to our problem.

Time Complexity: O(2 ^ n) - roughly in worst case with square board of size n.

Auxiliary Space Complexity: O(m + n) - since we need to store current path with positions.

Dynamic Programming

Let’s treat BOARD[i][j] as our sub-problem.

Since we have restriction of moving only to the right and down we might say that number of unique paths to the current cell is a sum of numbers of unique paths to the cell above the current one and to the cell to the left of current one.

  1. BOARD[i][j] = BOARD[i - 1][j] + BOARD[i][j - 1]; // since we can only move down or right.

Base cases are:

  1. BOARD[0][any] = 1; // only one way to reach any top slot.
  2. BOARD[any][0] = 1; // only one way to reach any slot in the leftmost column.

For the board 3 x 2 our dynamic programming matrix will look like:

011
0011
1123

Each cell contains the number of unique paths to it. We need the bottom right one with number 3.

Time Complexity: O(m * n) - since we’re going through each cell of the DP matrix.

Auxiliary Space Complexity: O(m * n) - since we need to have DP matrix.

Pascal’s Triangle Based

This question is actually another form of Pascal Triangle.

The corner of this rectangle is at m + n - 2 line, and at min(m, n) - 1 position of the Pascal’s Triangle.

References