Math solution, O(1) space

• This is a combinatorial problem and can be solved without DP. For mxn grid, robot has to move exactly m-1 steps down and n-1 steps right and these can be done in any order.

For the eg., given in question, 3x7 matrix, robot needs to take 2+6 = 8 steps with 2 down and 6 right in any order. That is nothing but a permutation problem. Denote down as 'D' and right as 'R', following is one of the path :-

D R R R D R R R

We have to tell the total number of permutations of the above given word. So, decrease both m & n by 1 and apply following formula:-

Total permutations = (m+n)! / (m! * n!)

Following is my code doing the same :-

``````public class Solution {
public int uniquePaths(int m, int n) {
if(m == 1 || n == 1)
return 1;
m--;
n--;
if(m < n) {              // Swap, so that m is the bigger number
m = m + n;
n = m - n;
m = m - n;
}
long res = 1;
int j = 1;
for(int i = m+1; i <= m+n; i++, j++){       // Instead of taking factorial, keep on multiply & divide
res *= i;
res /= j;
}

return (int)res;
}
}``````

• Why did you want m to be bigger? Is that just to minimize the for loop or does it actually affect the answer?

• No, it does not affect answer. One reason is sure to minimize for loop. Another reason is to avoid a possible number overflow. If m is taken to be higher, we can directly cancel m! part from the equation (m+n)! / (m! * n!) and so now we only calculate (m+1)(m+2)..(m+n) / n!
However, it does not affect even if m is smaller (or equal) number.

• Just as I thought. Thanks!

• How do you know that res will have j as a factor?

• @lee17: It can be proved formally. But this is the intuition : "We multiply k consecutive numbers before dividing by k". j starts with 1. We first multiply res with i and then divide by j. Let at some intermediate stage, j is 3. Then we have multiplied with 3 consecutive numbers, one of which is definitely a multiple of 3. Though we have removed 2 (by dividing by 2 previously), there is atleast one 3 available in res. Same can be said in general for any j.

• Same idea, with simpler code (Cpp).

``````class Solution {
public:
int uniquePaths(int m, int n) {
return nCr (m + n - 2, min(m, n) - 1);
}
private:
int nCr (int n, int r) {
long long_result = 1;
for (int i = 0; i != r; ++i) {
// from n - r + 1 (when i = 0) to n (when i = r - 1)
long_result *= (n - r + 1 + i);
// from 1 (when i = 0)         to r (when i = r - 1)
long_result /= (i + 1);
}
return (int) long_result;
}
};
``````

• @whitehat I think the swap step can be improved. m + n may be larger than Integer.MAX_VALUE. So, it would be better to use bitwise operation to swap.

• ``````int uniquePaths(int m, int n) {
double f1 = lgamma(m+n-1);
double f2 = lgamma(m);
double f3 = lgamma(n);
double f4 = f2+f3;
double f5 = f1-f4;
return round(exp(f5));
}
``````

A faster implementation of same using lgamma function

• My Python solution happens to be using the same idea

``````class Solution(object):
def uniquePaths(self, m, n):

totalMoves = m-1 + n-1

import math

def nCr(n,r):
f = math.factorial
return f(n) / f(r) / f(n-r)

return nCr(totalMoves, min([m,n])-1)
``````

• The answer is correct but I think if m and n become bigger, (m+n)! may exceed the range of int while DP solution is free from this problem :)

• This post is deleted!

• This post is deleted!

• Explanation for (m+n)!/(m! *n!):

If the matrix is 3x7, we have 10 grids to reach the finish because 3 + 7 = 10

The maximum right (The direction 'right' not right-wrong 'right') moves we can have is 3 since it's a 3x7 matrix.

The maximum down moves we can have is 7 since it's a 3x7 matrix.

No. of ways in which we can choose the right turn? It's C(10,3) = 10! / (7! * 3!) => (m+n)! / (m!*n!)

If you don't know what C(10,3) is, read about combinations here https://betterexplained.com/articles/easy-permutations-and-combinations/

• Thank you for your explanation.And there are my cpp codes base in your idea.

``````class Solution {
public:
int uniquePaths(int m, int n) {
if(n>m)
swap(m,n);
long long res=1;
for(int i=1;i<n;i++)
res=res*(m++)/i;
return int(res);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.