C++ 3 methods put together. You should use O(K) in interview. O(K^2) is not good.


  • 0
    C
        // O(N) time, O(N) space,  iterative
        vector<int> getRow(int rowIndex) {
            vector<int> ans(rowIndex+1, 0);
            ans[0] = 1;
            for(int i = 1; i <= rowIndex; i++) {
                ans[i] = (long long) ans[i-1] * (rowIndex-i+1) / i;
            }
            return ans;        
        }
    
        // O(N) time, O(N) space,  recursion
        vector<int> getRow(int rowIndex) {
            vector<int> ans(rowIndex+1, 0);
            helper(ans, rowIndex, rowIndex);
            return ans;
        }
        
        int helper(vector<int>& ans, int i, int j) {
            if(j == 0) return ans[j] = 1;
            return ans[j] = (long long)helper(ans, i, j-1) * (i-j+1)/j; 
        }
    
        // O(N^2) time, O(N) space,  recursion
        vector<int> getRow(int rowIndex) {
            vector<int> ans(rowIndex+1, 0);
            ans[0] = 1; 
            for(int i = 1; i <= rowIndex; i++) {
                for(int j = i; j >= 0; j--) {
                    ans[j] = ans[j] + (j-1>=0 ? ans[j-1] : 0);
                }
            }
            return ans;
        }
    

Log in to reply
 

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