[Java] Ways to traverse a grid

Given two integers N and M representing the number of rows and columns in a grid, calculate in how many ways we can traverse from top left to bottom right moving only right or down.

We can notice that the starting cell cannot be reached by moving, so we set its value to 0. All cells on the first row and column can only be reached in one way that is moving always right or down. We set them to 1.

All other cells can be reached by moving right or down from a previous left or top cell, which means they can be reached by continuing either of those paths, therefore they can be reached by summing up the ways of reaching the previous top and left cells.

This approach takes O(MN) time and space.

However it turns out there is a better approach that works in constant space and O(M+N) time.

Since each inner cell can be reached by summing some combinations of reaching previous cells, it means we are enumerating permutations of right and down movements up to a certain cell.

Therefore the magic fomula is (N+M)! / (N! * M!)

However, we need to use N-1 and M-1 as we are calculating the inner portion of a matrix where we actually move either direction, example:

0111

1###

1###

1###

We only do the calculation for the # cells as the boundary ones only offer one way of reaching them.

Because we only need to calculate three factorials, and the biggest is N+M, our runtime is O(N+M) - beware of overflows though!

You can check my implementations of waysToTraverseGrid and waysToTraverseGridCombinations on my Gist along with some tests in WaysToTraverseGridJTests.