Maze/Grid Puzzle – Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

his problem can also be solved using Combinations.

Think about it in this way:
There are in total m+n-2 steps from Start to End and n-1 (or m-1) “turning points” where we move from one column (or row) to the next one. Note that the “turning point” is not necessary to be a turn-left or turn-right point. For instance, moving from (i, j) to (i, j+1) can also be counted as a turning point since it moves to next column.

Now the question becomes how many ways we can choose n-1 (or m-1) turning points from the total steps, i.e. C(m+n-2, n-1). We only need to choose either row- or column-turning points since once those points are selected, the path has been determined. Obviously, the combination can be computed in O(min(m, n)) time with O(1) space.

public int uniquePaths(int m, int n) {  
   if (m == 0 || n == 0) return 0;  
   
   int x = Math.min(m, n), y = Math.max(m, n);  
   double count = 1;  
   for (int i=1; i
			

Leave a Reply

Your email address will not be published. Required fields are marked *