You are given the dimensions of a grid, m and n. Starting from the top left, or (0,0), you want to end up making your way to the bottom right corner. The only two moves you can make are to go one space directly to your right, or one space directly down. Write a function that can help you determine how many unique paths you can take between these two corners.
uniquePaths(3,2); // 3
uniquePaths(3,4); // 10
uniquePaths(7,3); // 24It might be helpful to draw this problem out for them if they can't visualize it themselves. The values in the cells are somewhat inconsequential and may even just be blank cells when you draw them out, but this might be a good start to guide them. See if the interviewee can draw this out first.
[
[1,1],
[1,1],
[1,1]
]
A 3x2 matrix should return 3 paths, corresponding to the following sets of directions
- right, down, down
- down, right, down
- down, down, right
At this point the interviewer should be asking you questions to clarify the problem statement. If they are not, prompt them: "Do you have any questions before we get started?" Some questions you may get:
- Can either m or n be 0? Yes. This should not change the problem.
As always, your interviewee should be looking to break this problem down if they can. Some helpful tips:
- Have them diagram a path for a small board. Maybe a
2x2or a3x2. - If their thoughts seem to be moving in the direction of dynamic programming, ask them what data structure they can use to capture their results as they build toward their solution (they can update their matrix).
- This problem can be solved recursively. As with all recursive problems, push your interviewees to think about their base and recursive cases. What is the smallest version of this problem they can solve? What would this problem look like for a
1x1matrix?1x2?2x2?
If your interviewee finishes, have them review:
- Time and space complexity of their solution
- If they've discussed the recursive approach, see if they can talk through the DP approach, and vice versa.
- What is the trade-off between the DP and recursive approaches?
For some, it may be easiest to think about this problem recursively. Think about fanning out from your starting point in each available direction (right and down), counting the ways you can reach your target matrix[m-1][n-1] at each cell, and bubbling that response back up.
When you reach matrix[m-1][n-1], you can return 1 to indicate that you've discovered a valid path. If you've exceeded the dimensions of the grid in your search, you can return a 0 to indicate that your search was not fruitful. These your two base cases.
Time: O(M*N)
Space: O(M*N)
For this problem, the space complexity comes in the form of each recursive call building onto the call stack. What happens when our inputs get larger and larger? Recall the dreaded "Maximum Callstack Size Exceeded" error. This extra space on the call stack makes this implementation less efficient overall, especially with larger inputs.
// initialize default value of 0 for column and row
function uniquePaths(m, n, row = 0, col = 0) {
// if we've reach our target cell, we know we've found a valid path
// return 1 so that we can increment our count of unique paths
if (row === m - 1 && col === n - 1) {
return 1;
// if we are trying to check a cell outside the limits of our grid, return 0
} else if (row >= m || col >= n) {
return 0;
// in every other case, add up the unique paths we can find by looking to the right or looking down
} else {
return uniquePaths(m, n, row, col + 1) + uniquePaths(m, n, row + 1, col);
}
}This approach improves on our recursive solution. We can reduce the load on the call stack by using memoization. Notice that in our previous approach, our call stack for our recursive would not unwind until we hit our base cases, potentially building up until we went from one end of a very large grid to another.
Here we borrow an approach we used in the DP solution above and create a grid that we can record results in. We can access values from the grid like a cache so we don't need to recalculate possible paths for every cell. While this introduces another data structure to our implemetation, we benefit by invoking our recursive findPaths function fewer times.
Time: O(M*N)
Space: O(M*N)
function uniquePaths(m, n) {
// initialize an m x n matrix filled with 0s
const matrix = Array(m);
for (let row = 0; row < m; row++) {
matrix[row] = Array(n).fill(0);
}
return findPaths(matrix);
}
function findPaths(memo, row = 0, col = 0) {
// The first two branches of our condition are the same as before
if (row === memo.length - 1 && col === memo[0].length - 1) {
return 1;
} else if (row >= memo.length || col >= memo[0].length) {
return 0;
// If we haven't seen the value before, calculate and set the value in the corresponding cell
// Otherwise, we can assume that the cell contains a value from a previous call to this function and do not need to perform any new calculations
} else if (!memo[row][col]) {
memo[row][col] = findPaths(memo, row, col + 1) + findPaths(memo, row + 1, col);
}
// Finally, return the value in the desired cell
return memo[row][col];
}A different method of solving this problem entirely involves using dynamic programming to calculate the number of possible paths it takes to get to each cell. With 3x4 grid, for example, we can create a matrix with our given dimensions immediately off the bat to maintain a record of how many paths we can take to a given cell.
// initial matrix
[
[ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ]
]
Since the only moves we can make are to go right or down, we can deduce that the number of paths it takes to get to a given cell should be the sum of the values in the cells immediately to its left and above it. The 0th row and 0th columns are easy--there is only one way to get to these cells, and it's to go in the same direction starting from matrix[0][0]. All subsequent cells can be calculated by iterating through the matrix and summing adjacent cells to produce the following result, where the cell at matrix[m-1][n-1] contains the answer to our prompt.
// after iterating through row 1
[
[ 1, 1, 1, 1 ],
[ 1, 2, 3, 4 ],
[ 1, 1, 1, 1 ]
]
// after iterating through row 2
[
[ 1, 1, 1, 1 ],
[ 1, 2, 3, 4 ],
[ 1, 3, 6, 10 ]
]
Time: O(M*N)
Space: O(M*N)
function uniquePaths(m, n) {
// initialize an m x n matrix filled with 1s
const matrix = Array(m);
for (let row = 0; row < m; row++) {
matrix[row] = Array(n).fill(1);
}
// iterate through the matrix, starting from the row at index 1
for (let row = 1; row < m; row++) {
// iterate through the row starting from the column at index 1
for (let col = 1; col < n; col++) {
// set the value of the current cell to the calculated value of possible paths to arrive at our current cell
matrix[row][col] = matrix[row - 1][col] + matrix[row][col - 1];
}
}
return matrix[m - 1][n - 1];
}- Memoization may take up more space, but can help reduce the resources needed to perform calculations over and over.
- Dynamic programming is a handy tool for incrementally building up answers to complex problems.