Coding Interview Questions | Unique Paths

February 6th, 2024

Unique Paths Problem Introduction:

This summary will talk about my solution to the unique paths problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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.

How do you solve the Unique Paths Problem using Dynamic Programming?

Solution:

function uniquePaths(m: number, n: number): number {
  const matrix = Array.from({ length: m }, () =>
    Array.from({ length: n }, () => 0)
  );
  matrix[0][0] = 1;

  for (let rowIdx = 0; rowIdx < m; rowIdx++) {
    for (let colIdx = 0; colIdx < n; colIdx++) {
      if (rowIdx === 0 && colIdx === 0) {
        continue;
      }
      const leftIdx = colIdx - 1;
      const topIdx = rowIdx - 1;

      const leftVal = leftIdx >= 0 ? matrix[rowIdx][leftIdx] : 0;
      const topVal = topIdx >= 0 ? matrix[topIdx][colIdx] : 0;
      matrix[rowIdx][colIdx] = leftVal + topVal;
    }
  }
  return matrix[m - 1][n - 1];
}

Unique Paths Solution Summary:

Below is a breakdown of the key aspects of the solution above for the unique paths problem:

1. Matrix Initialization:

The algorithm initializes a 2D matrix of size m x n representing the grid. Each cell is initially set to 0, except for the top-left corner (matrix[0][0]), which is set to 1 as the starting point.

2. Iterative Path Calculation:

The solution utilizes nested loops to iterate through each cell of the matrix. For each cell, it calculates the number of unique paths to reach that cell by summing the paths from the left (leftVal) and the paths from the top (topVal).

3. Handling Boundary Conditions:

The algorithm efficiently handles boundary conditions, ensuring that calculations for the left and top values are valid (i.e., within the matrix bounds).

4. Dynamic Programming:

By filling in the matrix iteratively, the algorithm employs a dynamic programming approach to build up solutions for subproblems and eventually obtain the total number of unique paths to the bottom-right corner.

5. Result Retrieval:

The final result is obtained from the bottom-right corner of the matrix (matrix[m - 1][n - 1]), representing the total number of unique paths from the top-left to the bottom-right corner.

Complexities:

1. Time Complexity:

The time complexity is determined by the nested iteration through the matrix (m x n). The algorithm has a time complexity of O(m * n).

2. Space Complexity:

The space complexity is O(m * n) as the algorithm uses a matrix of size m x n to store the number of unique paths for each cell.