Unique Paths Problem

20 Aug, 2019

A robot is located at the top-left corner of a m x n grid. 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. How many possible unique paths are there?

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

Example #1

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 -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example #2

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

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:

                START
                /   \
               D     R
             /     /   \
           R      D      R
         /      /         \
        R      R            D

       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.

/**
 * BACKTRACKING approach of solving Unique Paths problem.
 *
 * @param {number} width - Width of the board.
 * @param {number} height - Height of the board.
 * @param {number[][]} steps - The steps that have been already made.
 * @param {number} uniqueSteps - Total number of unique steps.
 * @return {number} - Number of unique paths.
 */
export default function btUniquePaths(
  width,
  height,
  steps = [[0, 0]],
  uniqueSteps = 0
) {
  // Fetch current position on board.
  const currentPos = steps[steps.length - 1]

  // Check if we've reached the end.
  if (currentPos[0] === width - 1 && currentPos[1] === height - 1) {
    // In case if we've reached the end let's increase total
    // number of unique steps.
    return uniqueSteps + 1
  }

  // Let's calculate how many unique path we will have
  // by going right and by going down.
  let rightUniqueSteps = 0
  let downUniqueSteps = 0

  // Do right step if possible.
  if (currentPos[0] < width - 1) {
    steps.push([currentPos[0] + 1, currentPos[1]])

    // Calculate how many unique paths we'll get by moving right.
    rightUniqueSteps = btUniquePaths(width, height, steps, uniqueSteps)

    // BACKTRACK and try another move.
    steps.pop()
  }

  // Do down step if possible.
  if (currentPos[1] < height - 1) {
    steps.push([currentPos[0], currentPos[1] + 1])

    // Calculate how many unique paths we'll get by moving down.
    downUniqueSteps = btUniquePaths(width, height, steps, uniqueSteps)

    // BACKTRACK and try another move.
    steps.pop()
  }

  // Total amount of unique steps will be equal to total amount of
  // unique steps by going right plus total amount of unique steps
  // by going down.
  return rightUniqueSteps + downUniqueSteps
}

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.

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

Base cases are:

BOARD[0][any] = 1; // only one way to reach any top slot.
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:

0 1 1
0 0 1 1
1 1 2 3

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.

/**
 * DYNAMIC PROGRAMMING approach of solving Unique Paths problem.
 *
 * @param {number} width - Width of the board.
 * @param {number} height - Height of the board.
 * @return {number} - Number of unique paths.
 */
export default function dpUniquePaths(width, height) {
  // Init board.
  const board = Array(height)
    .fill(null)
    .map(() => {
      return Array(width).fill(0)
    })

  // Base case.
  // There is only one way of getting to board[0][any] and
  // there is also only one way of getting to board[any][0].
  // This is because we have a restriction of moving right
  // and down only.
  for (let rowIndex = 0; rowIndex < height; rowIndex += 1) {
    for (let columnIndex = 0; columnIndex < width; columnIndex += 1) {
      if (rowIndex === 0 || columnIndex === 0) {
        board[rowIndex][columnIndex] = 1
      }
    }
  }

  // Now, since we have this 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.
  for (let rowIndex = 1; rowIndex < height; rowIndex += 1) {
    for (let columnIndex = 1; columnIndex < width; columnIndex += 1) {
      const uniquesFromTop = board[rowIndex - 1][columnIndex]
      const uniquesFromLeft = board[rowIndex][columnIndex - 1]
      board[rowIndex][columnIndex] = uniquesFromTop + uniquesFromLeft
    }
  }

  return board[height - 1][width - 1]
}

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.

/**
 * @param {number} lineNumber - zero based.
 * @return {number[]}
 */
function pascalTriangle(lineNumber) {
  const currentLine = [1]

  const currentLineSize = lineNumber + 1

  for (let numIndex = 1; numIndex < currentLineSize; numIndex += 1) {
    // See explanation of this formula in README.
    currentLine[numIndex] =
      (currentLine[numIndex - 1] * (lineNumber - numIndex + 1)) / numIndex
  }

  return currentLine
}

/**
 * @param {number} width
 * @param {number} height
 * @return {number}
 */
export default function uniquePaths(width, height) {
  const pascalLine = width + height - 2
  const pascalLinePosition = Math.min(width, height) - 1

  return pascalTriangle(pascalLine)[pascalLinePosition]
}

Same series:

Advanced Algorithms