Clean Solution, O(m*n) space O(m*n) time - Unique Paths


  • 0
    W

    Codes go here:

    class Solution {
    public:
        int uniquePaths(int m, int n) {
            if(m == 1 || n == 1) { // always go down or go right
                _m[make_pair(m, n)] = 1;
                return 1;
            }
            pair<int, int> down = make_pair(m-1, n),  // go down
                           right = make_pair(m, n-1); // go right
            if(_m.count(down) == 0) _m[down] = uniquePaths(m-1, n);
            if(_m.count(right) == 0) _m[right] = uniquePaths(m, n-1);
            return _m[down]+_m[right];
        }
        
    private:
        map<pair<int, int>, int> _m; // to save time
    };
    

    Space cost is easy to tell - just _m, which is O(mn). Time cost is a little difficult to tell: the solution is fill in the map, and map size is O(mn). So ...^ ^


  • 0
    G

    not a good space complexity.
    check this out (O(n) space).

    class Solution {
    public:
        int uniquePaths(int m, int n) {
            vector<int> lastRow(n+1, 1);
            lastRow[0] = 0;
            for (int row=2; row<=m; row++) {
                for (int col=1; col<=n; col++) {
                    int curr = lastRow[col-1] + lastRow[col];
                    lastRow[col] = curr;
                }
            }
            
            return lastRow[n];
        }
    };

Log in to reply
 

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