LeetCode 62: Unique Paths

Many LeetCode problems involve moving around a maze or grid. Mazes tend to be modeled as graphs, but for some problems of this type, dynamic programming is the right approach. We’ll see that in this week’s problem, LeetCode 62: Unique Paths.

Unique Paths takes only the two integers m and n as input, representing the dimensions of a grid with m rows and n columns. The goal is to calculate the number of paths that a robot could take from the top-left, at position (0, 0) to the bottom-right, at position (m-1, n-1). The robot can only move down and right.

Two things to keep in mind:

• This is not a maze problem, since there are no walls other than the edges of the grid. Every position is open.

• We don’t need to store the paths from start to finish, or find the shortest path from start to finish. The goal is to count the paths. Counting is a common application of dynamic programming. For DP counting problems, the memo table contains counts.

Two implementation decisions we need to make for this problem: 1) Should we move from Start to Finish, or from Finish to Start, and; 2) Should we implement a Top-Down solution or a Bottom-Up solution?

Any combination of these two approaches will work. I’ll describe the one that I found most intuitive, which is 1) Finish to Start, and 2) Bottom-Up.

Base Cases

If m == 1 or n == 1, then there’s only one path: directly from Start to Finish, either down to the finish or right to the finish. So the path count is 1 in this case.

For grids with m > 1 and n > 1, consider the four cells at the bottom right corner. The goal is to get to the Finish position at cell F:

-----
|C|D|
-----
|E|F|
-----

From cell C, we have two options: move right to D, or down to E.

Cell D or E give us only one choice each: down to the finish from D, or right to the finish from E. So there are two unique paths from C: right-down and down-right.

Generalizing this idea: If this four-cell block is placed somewhere in the grid, the number of unique paths to the finish from C is the sum of the number of unique paths to the finish from D plus the number of unique paths to the finish from E. (We can’t get to F in one move, since we can’t move diagonally).

Bottom-Up

To implement this idea with a bottom-up approach, we’ll need to handle a few special cases:

• If C is in the last column, then D is past the right edge of the grid, so it contributes 0 paths.

• If C is in the last row, then E is past the bottom edge of the grid, so it contributes 0 paths.

• If C is in the last column and the last row, then we’re at the Finish cell. To avoid getting a sum of 0 + 0 = 0 in this case, we’ll need to initialize a cell to 1.

The simplest way to handle these special cases is to store counts in a 2D array of size m+1 x n+1, with the extra row and column used to avoid the need for boundary checks. We’ll initialize the array to 0, except for one cell initialized to 1, the out-of-bounds cell either to the right of or below the finish cell. We could use less space if we didn’t store the whole grid, since we only need adjacent cells when calculating the count for a cell. To keep the code short, I’ll go with this simpler approach.

When we solved Longest Common Subsequence, we looped from right to left and bottom to top. If we do the same for this problem and store counts in an array dp, then dp[row][col] stores the number of unique paths from (row, col) to (m-1, n-1), and our solution will be in dp[0][0] when we finish.

Pseudocode

if m == 1 or n == 1
    return 1  // there's only one path in a 1xn or mx1 grid

create array dp of size [m+1][n+1]
dp[m][n-1] = 1  // initialize out-of-bounds cell to start the counting

for row from m-1 to 0
    for col from n-1 to 0
        // two options: move right or move down
        dp[row][col] = dp[row+1][col] + dp[row][col+1]

// number of paths from start position
return dp[0][0]

References

For multiple implementations, including a fancy math solution, see archit91’s editorial on LeetCode.

(Image credit: DALL·E 3)

For an introduction to this year’s project, see A Project for 2024.