C++ Pure math solution, O(min(m, n)) time complexity, O(1) space complexity


  • 0
    A

    Simple combinatorics, but I didn't realize the number could be extremely large to fit in integer type.

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

Log in to reply
 

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