Pascal's Triangle [ Logic + Solution ] in bits

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Input: numRows = 5 | Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

• According to the question, it is given the number of rows, which means we have to make the loop run till provided integer.

• On noticing the GIF of Pascal's triangle we can see the index of the row has the same size as the array

  1. [0] 1st row -> 1
  2. [1] 2nd row -> 1, 1
  3. [2] 3rd row -> 1, 2, 1
  4. [3] 4th row -> 1, 3, 3, 1

• Another thing we can notice is the pascal triangle each row's starting and end index has a value of 1.

• Now, we can assemble this as running a nested loop which runs for each parent loop index which makes it run till that number, if is parent index is 3 for the 3rd row then the child loop index only runs at the same number of time.

• Also, creating a new vector at each beginning of the parent loop, will have a dynamic size for the number of rows and all values will be 1.

vector<int>sample(i+1,1);

• The child loop starts from the index [2] or 3rd row because that is where we are adding values of the previous row 2nd [1] i.e [1, 1].

// child loop / nested loop

for(int j = 1; j<i;j++){
      // only runs when i became 2
}

• About the parent loop now,

for(int i = 0; i<numRows; i++){ // parent loop

      vector<int>sample(i+1,1);

      for(int j = 1; j<i;j++){ // child loop
            // only runs when i became 2
       }

       res.push_back(sample);
}

• On 0, the child will not run and the sample will create a vector of size 1 with a value of [1] and push_back to res.

• On 1, the child will not run and the sample will create a vector of size 1 with a value of [1, 1] and push_back to res.

• Now the child will run and take 1 round to add the value like this:

sample[j]=res[i-1][j-1]+res[i-1][j];

// On i = 2, res[2-1][1-1] + res[2-1][1]
//                res[1][0] + res [1][1]
//                1 + 1 = 2
// sample[1] = 2, while sample is of size 0 and 1,2,1 is stored

Final Code

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        // We can't decide the size initially while pushing the array to it

        for(int i = 0; i<numRows; i++){

            vector<int>sample(i+1,1);

            for(int j = 1; j<i;j++){
                sample[j]=res[i-1][j-1]+res[i-1][j];
            }

            res.push_back(sample);
        }

        return res;
    }
};

Now we understood the code in chunks 🤩.

Question link on leetcode.