62. Unique Paths

How to solve Unique Paths (LeetCode 62): the approach in brief

The 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.

Pattern

Unique Paths is a Dynamic Programming (DP) Patterns problem, in the 2D Array (Unique Paths on Grid) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Count paths and find optimal paths in grids using 2D dynamic programming.

Approach outline

1. Consider using dynamic programming to solve this problem efficiently, as it involves counting the number of ways to reach a point on a grid.
2. Think about how the number of unique paths to a particular cell depends on the paths to the cells immediately above and to the left of it.
3. Try to define a 2D DP array where each element represents the number of unique paths to that cell.

Complexity

The reference solution runs in O(m * n) time and O(n) space.

Asked at

Unique Paths has been reported in interviews at Amazon, Bloomberg, ByteDance, Facebook, Goldman Sachs, Google, Microsoft, Qualtrics.