A robot is located at the top-left corner of a m x n grid
(marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Example #1
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 -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example #2
Input: m = 7, n = 3
Output: 28
With this problem, try to guide your interviewee to look for a pattern in the grid and its result. To help them see the pattern, you can ask them to step through multiple example inputs of m or n. If they skip the Example part, try to guide your interviewee back on track by asking to test additional examples in the diagram to see how the pattern in the grid grows. If they dont see it, point out how frequently they're having to repeat and count the same steps from previous squares and ask if there is a way for them to keep track of the work they've already done. Does that sound like recursion OR DP??
Recursion - If they are going the recursive route, mention memoization as something they can use and attempt to implement from Thursday's algo. If you're in the first row or the first column, there is only one path you can take to get there. As you continue your path inwards, one can begin to notice the pattern where you're adding the previous steps you've taken from the top and left squares of the square you would like to end up.
DP - If your interviewer sees the pattern above and is trying to visualize the grid with a Data Structure, it might help to mention that they can dynamically build the solution with a DP matrix(arrays inside of an array). You want to set up your grid with the base cases where every square will take ATLEAST 1 step. As you loop through your grid, you are only looking at the most steps it will take to get to that square from the top and the left squares. Those steps will be represented as the values inside of those squares and they will dynamically change as you loop through the entire grid.
recursiveUniquePaths = (m, n) => {
// if we're in Row 1 or Column 1, return 1 as there's only one route to these locations
if (m === 1 || n === 1) return 1;
// otherwise return the sum of the number of routes to the node above and the node to the left
return recursiveUniquePaths(m - 1, n) + recursiveUniquePaths(m, n - 1)
}
// with memoization
recursiveUniquePaths = (m, n, memo = Array(m + 1).fill([]).map(() => {
return Array(n + 1).fill(null)) => {
// if we're in Row 1 or Column 1, return 1 as there's only one route to these locations
if (m === 1 || n === 1) return 1;
// calculate a new value if the memo is undefined
if (memo[m][n] === null) {
memo[m][n] = recursiveUniquePaths(m - 1, n, memo) + recursiveUniquePaths(m, n - 1, memo);
}
return memo[m][n];
}
Time Complexity:
- Without Memoization:
O(2 ^ n)- roughly in worst case with square board of sizen. - With Memoization:
O(m * n)- since we're going through each cell of the DP matrix.
Space Complexity: O(m + n) - since we have up to m + n calls on the stack at any given time.
Let's treat BOARD[i][j] as our sub-problem.
Since we have restriction of moving only to the right and down we might say that number of unique paths to the current cell is a sum of numbers of unique paths to the cell above the current one and to the cell to the left of current one.
BOARD[i][j] = BOARD[i - 1][j] + BOARD[i][j - 1]; // since we can only move down or right.
Base cases are:
BOARD[0][any] = 1; // only one way to reach any top slot.
BOARD[any][0] = 1; // only one way to reach any slot in the leftmost column.
For the board 3 x 2 our dynamic programming matrix will look like:
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 |
Each cell contains the number of unique paths to it. We need
the bottom right one with number 3.
const uniquePaths = (m, n) => {
// create an base array full of '1' as there is at least 1 path to each of the edge nodes
let solutionArray = Array(m).fill([]).map(() => {
return Array(n).fill(1);
});
// iterate over the rows and columns, excluding the row and column at index 0 which should stay at 1
for (let row = 1; row < m; row++) {
for(let column = 1; column < n; column++) {
// set each item in the array equal to the number of routes above plus the number of routes to the left
solutionArray[row][column] = solutionArray[row -1][column] + solutionArray[row][column - 1]
}
}
return solutionArray[m-1][n-1];
}
Time Complexity: O(m * n) - since we're going through each cell of the DP matrix.
Space Complexity: O(m * n) - since we need to have DP matrix.
- LeetCode Feel free to send this link to your interviewee to test their code unless they prefer a repl.