My Brief and Fast C++ solution (4ms), No Extra Space, Good Locality


  • 4
    P

    No need to dynamically allocate or deallocate space by push_back or insert.

    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> res = vector<int>(rowIndex + 1, 1);
            
            // 0-indexed rows
            for (int row = 1; row <= rowIndex; ++ row)
                // Reverse the order so no extra space needed
                for (int i = row - 1; i > 0; -- i)
                    res[i] += res[i - 1];
            
            return res;
        }
    };

  • 0
    J

    It is an interesting solution I just wanted to share. You don't need to initialize all elements to 1.

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

Log in to reply
 

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