Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

Number of paths in 2D matrix

Puzzle: Given a 2D matrix with N rows and M columns.
You have to move from upper left corner to diagonally opposite, lower right corner.
If only valid moves at any given cell are Move 1 cell Right or Move 1 cell down, then
calculate the total number of ways in which you can move from source to destination.

Solution: In any path, total moves required to move from start to end are N+M-2

Out of these, (N-1) moves must be down and (M-1) moves must be towards right.

(N-1) moves can be chosen from (N+M-2) moves in N+M-2CN-1 ways.

So total number of ways to move are also the same = N+M-2CN-1 = (N+M-2)! / (N-1)! (M-1)!

Verification:

For 3x2 matrix, ways = 3!/2!1! = 3

For 3x3 matrix, ways = 4!/2!2! = 6

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: