# 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
```