Math solution, O(1) space


  • 52
    W

    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;
        }
    }

  • 0
    C

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


  • 1
    W

    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.


  • 0
    C

    Just as I thought. Thanks!


  • 0
    L

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


  • 3
    W

    @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.


  • 0
    L

    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;
        }
    };
    

  • 0
    O

    @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.


  • 1
    T
    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


  • 0
    X

    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)
    

  • 1
    I

    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 :)


  • 0
    I
    This post is deleted!

  • 0
    T
    This post is deleted!

  • 0
    T

    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/


Log in to reply
 

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