Unique Paths
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
A robot at the top-left of an m x n grid can move only right or down. How many different paths reach the bottom-right?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many paths reach any cell of the first row? The first column?
- Hint 2Fill the table row by row, each cell from its two neighbours.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A city with square blocks; you walk only east or south from your home at the north-west corner to a cafe at the south-east. At each crossing, the number of ways to get there is the number of ways to the crossing just north plus the number of ways to the crossing just west. The first row and first column have exactly one way (straight line).
- The obvious way
Recursion from the corner recomputes cells: O(2^(m+n)).
- The key insight
Keep one row of counts, all 1 at first. For every further row, go left to right and add the cell on the left into the current cell (the current cell already holds the count from above). The last cell is the answer.
- The algorithm
- Row of ones.
- For each next row, for each cell except the first: cell += cell on its left.
- Repeat for all rows.
- Return the last cell.
Watch it run
Examplem = 3 rows, n = 3 columns
Top row: one way to each crossing (straight east).
1 1 1
Where people slip
- Math also works: choose which m - 1 of the m + n - 2 moves are down, C(m+n-2, m-1).
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def unique_paths(m, n):
ways = [1] * n # the first row: one way to each crossing
for _ in range(m - 1):
for column in range(1, n):
ways[column] += ways[column - 1] # from above (already there) + from the left
return ways[n - 1]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.