My O(1) space solution


  • 0
    R
    vector<int> getRow(int rowIndex) 
    {
        if(rowIndex < 0) return vector<int>();
        
        vector<int> res(rowIndex+1);
        if(rowIndex == 0) 
        {
            res[0] = 1;
            return res;
        }
        
        int t1, t2;
        
        for(int i = 1; i <= rowIndex; i++)
        {
            res[0] = res[i] = 1; 
            t1 = res[0];
            t2 = res[1];
            for(int j = 1; j < i; j++)
            {
                res[j] = t1 + t2;
                t1 = t2;
                t2 = res[j+1];
            }
        }
        return res;     
    }
    

    Allocate needed space for return vector at the beginning. Use two temps to do in-place overwrite.


  • 7
    I

    Here is my solution with O(1) space too.

    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> result(rowIndex+1, 1);
            for(int i=0; i<=rowIndex; i++) {
                for(int j=i-1; j>=1; j--) {
                    result[j] = result[j-1] + result[j];
                }
            }
        return result;
        }
    };
    

  • 0
    J

    Awesome! Very nice answer!


  • 0
    N

    Excellent ! I guess you should make the triangle left-aligned, and found the solution.


  • 0
    Q

    i don't know about C++ but this is clearly a O(k) in java... since u r storing the elements in the array (vector)...


Log in to reply
 

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