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

• 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 ...^ ^

• 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];
}
};``````

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