[Solution] Matrix-num-paths | Facebook Interview Question
This problem was asked by Facebook.
There is an
M matrix of zeroes. Given
M, write a function to count the number of ways of starting at the
top-left corner and getting to the
bottom-right corner. You can only move
For example, given a
2 matrix, you should return
2, since there are
two ways to get to the
- Right, then down
- Down, then right
5 matrix, there are
70 ways to get to the
Idea behind the solution
s(n, m) be the number of paths for a matrix of size
m. Knowing that
s(2, 2) = 4, it can be shown that the solution for
s(2, 2) = s(1, 2) + s(2, 1).
First, consider the matrix
0 0 0 0
At the top-left corner we have only 2 options, first start going right or going down. If we choose start going right, the remaining possibilities would look like:
Therefore, we need to solve the number of paths for the matrix
On the other hand, if we had choosen to go down, the remaining possibilities would be as follows:
In other words, the matrix
1x2 is left.
Clearly, the number of paths for the matrix
1x2 to go to it's
1 respectively. Combining those 2 solutions, the possibilities for
s(2, 2) = s(1, 2) + s(2, 1) = 2.
Applying the same logic for the matrix
0 0 0 0 0 0
s(3, 2) = s(2, 2) + s(3, 1) = 2 + 1 = 3
For the matrix
0 0 0 0 0 0 0 0 0
s(3, 3) = s(3, 2) + s(2, 3) = 5 + 5 = 10.
Note that, by remembering small solutions we can quickly calculate the number of paths for the current matrix. This is an instance of Dynamic Programming. By using a table
s[i][j] that gives the solution for the matrix
ixj, we can fill this table starting from s until we get to the desidered size.
Please check the main.js snippet for the solution.
This solution originally posted at: Github by @Murillo2380