62. Unique Paths

Prompt

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.

Input: m = 3, n = 7
Output: 28
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 -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Approach

You’re given a m x n grid and a robot is 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]) and can only move either down or right.

  1. Bottom-Up Dynamic Programming
  1. We’ll want to index into our cache or auxiliary data structure at the specific row then specific column of the subproblem and check if it’s greater than 0. If so, we’ll want to return the value of the cache at that specific row and column.
  2. Lastly, we’ll want to check if the row and column of the subproblem is equal to the total # of rows and columns-1 or in other words, the last row and column indicating that we’re at our destination position within the grid. If we are at this position, then we want to return 1 indicating that there is a valid path.

Code

Python | Time: O(m * n) | Space: O(m * n)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com