Java O(1) space and O(min(m,n)) time (in multiply and divide)


  • 0
    C

    public int uniquePaths(int m, int n) {
         if(m <= 1 || n <= 1) return 1;
         return getCombination(m + n - 2, Math.min(m, n) - 1);
    }
    int getCombination(int a, int b){
         long result = a;
         for(int i = 2; i <= b; i++){
             result *= a + 1 - i;
             result /= i;
         }
         return (int)result;
    }

    Tips:
    From starting point to ending point, you have to go m+n-2 steps no matter how you move. Among them, there are m-1 horizontal and n-1 vertical moves. So, it is simply a combination choosing m-1 or n-1 from m+n-2.


Log in to reply
 

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