Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

LeetCode 62: Unique Paths

By Duncan Smith Mar 27 0

Robot on a grid

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.

Categories: LeetCode

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • 2023 in Review: 50 LeetCode Tips
  • 2022 in Review: Content Bots
  • 2021 in Review: Thoughts on Solving Programming Puzzles
  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • Do Coding Bots Mean the End of Coding Interviews? December 31, 2024
  • Another Project for 2024 May 8, 2024
  • Dynamic Programming Wrap-Up May 1, 2024
  • LeetCode 91: Decode Ways April 24, 2024
  • LeetCode 70: Climbing Stairs April 17, 2024
  • LeetCode 221: Maximal Square April 10, 2024
  • Using Dynamic Programming for Maximum Product Subarray April 3, 2024
  • LeetCode 62: Unique Paths March 27, 2024
  • LeetCode 416: Partition Equal Subset Sum March 20, 2024
  • LeetCode 1143: Longest Common Subsequence March 13, 2024
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2025 Duncan Smith