Does this solution use O(n) space?


  • 0
    W

    I create the variable cnk only n/2 times,does it still O(n) space?

    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
        int n = rowIndex;
    	vector<int> res(n+1);
    	res[0]= res[n] = 1;
    	for (int k = 1; k < n; ++k){
    		if (k > n - k) res[k] = res[n-k];
    		if (!res[k]){
    			long long cnk = 1;
    			for (int i = 1; i <= k; ++i){
    				cnk = cnk * (n - i + 1) / i;
    			}
    			res[k] = cnk;
    		}
    	}
    	return res;
        }
    };

Log in to reply
 

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