You're driving in New York city, represented as the grid below. You start at the top-left corner of the city, and can either drive South or East. You need to get to the bottom-right corner of the city to win a prize.
Assume the city is n
x m
blocks large. Return the number of ways you can get to the bottom-right corner.
Example:
Explanation: There are 3 unique paths that lead to the coin.
1. Recursion
To solve this problem, we want to find the number of paths that lead into the bottom right corner. We can write a recursion that computes the number of paths that lead into a particular square.
The the number of ways get to any square is equal to the number of ways to get to that square from the top, plus the number of ways to get to it from the left.
2. Base case
The recursion will keep calling itself on smaller m
's and n
's, until it gets to a square that's out of bounds. You need a base case for when this happens. There are no ways for your car to get out of bounds:
You also need a base case to indicate that you start at the top left corner.
3. Code
You can code this up using regular recursion, but it's very slow.
You'll get a Time Limit Exceeded error if you run this code.
To code this up, you can use "Tabulation". The function call
numPaths(m, n)
depends on numPaths
of smaller m
and n
, so we can compute the smallest m
and n
first and the biggest ones last. Here's the code:
Time Complexity O(n⋅m)
Space Complexity O(n⋅m)
You don't have to know this for an interview, but you can solve this problem with only math. The car always steps right n-1 times, and down m-1 times, giving m-n-2 steps total. Out of all these steps, we want to choose m-1 of them to be down steps, and the rest of them to be right steps (or we could choose the other way, it doesn't matter). You can write this with math as:
Here's how you can code this up.
Time Complexity O(1)
Space Complexity O(1)