[Solution] Matrix-num-paths | Facebook Interview Question
This problem was asked by Facebook.
There is an N
by M
matrix of zeroes. Given N
and 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 right
or down
.
For example, given a 2
by 2
matrix, you should return 2
, since there are two ways
to get to the bottom-right
:
- Right, then down
- Down, then right
Given a 5
by 5
matrix, there are 70
ways to get to the bottom-right
.
Idea behind the solution
Let s(n, m)
be the number of paths for a matrix of size n
, 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 2x2
:
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:
0 0
Therefore, we need to solve the number of paths for the matrix 2x1
On the other hand, if we had choosen to go down, the remaining possibilities would be as follows:
0 0
In other words, the matrix 1x2
is left.
Clearly, the number of paths for the matrix 2x1
and 1x2
to go to it's bottom-right
is 1
and 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 3x2
:
0 0 0 0 0 0
s(3, 2) = s(2, 2) + s(3, 1) = 2 + 1 = 3
For the matrix 3x3
:
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[1][1] until we get to the desidered size.
Please check the main.js snippet for the solution.
This solution originally posted at: Github by @Murillo2380
Comments
Leave a comment
You are not LoggedIn but you can comment as an anonymous user which requires manual approval. For better experience please Login.