Short C++ solution using only O(k) extra space


  • 8

    Starting with empty array. Because row i + 1 is longer than row i by 1, and the last number in each row is always 1.

    So suppose we are just done with row i, when when proceed with row i + 1:

    1. We need to push a "1" to the current array first we have (with row i's result),

    2. Then update index 1 through i. Observing that first number of array always will be 1 too, which doesn't need to be updated since we already did that when we deal with row 0 (last and first index are both 0 for row 0).

      class Solution {
      public:
      vector<vector<int>> generate(int numRows) {
      vector<vector<int>> result;

           vector<int> row;
           for(int i = 0; i < numRows; i++){
               row.push_back(1);
               for(int j = i - 1; j > 0; j--){
                   row[j] = row[j - 1] + row[j];
               }
               result.push_back(row);
           }
           
           return result;
       }
      

      };


  • 0
    A

    @Ximin-Z it is an really interesting idea just using one vector, thanks for your idea


Log in to reply
 

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