Pascal's Triangle

Problem Description

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.

Examples

Example 1:

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

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints

• $1 <= numRows <= 30$

---

Solution for Binary Tree Problem

Intuition And Approach

To generate Pascal's triangle, we start with the first row [1]. Each subsequent row is generated by adding the number above and to the left with the number above and to the right. We append 1 at the beginning and end of each row.

• Recursive

Code in Different Languages

Java

Written by @Vipullakum007

class Solution {
 public List<List<Integer>> generate(int numRows) {
     List<List<Integer>> triangle = new ArrayList<>();

     if (numRows == 0) {
         return triangle;
     }

     // First row
     triangle.add(new ArrayList<>());
     triangle.get(0).add(1);

     for (int rowNum = 1; rowNum < numRows; rowNum++) {
         List<Integer> row = new ArrayList<>();
         List<Integer> prevRow = triangle.get(rowNum - 1);

         // First element is always 1
         row.add(1);

         // Each triangle element (except the first and last of each row)
         for (int j = 1; j < rowNum; j++) {
             row.add(prevRow.get(j - 1) + prevRow.get(j));
         }

         // Last element is always 1
         row.add(1);

         triangle.add(row);
     }

     return triangle;
 }
}

Python

Written by @Vipullakum007

 class Solution:
 def generate(self, numRows: int) -> List[List[int]]:
     triangle = []

     for row_num in range(numRows):
         row = [1] * (row_num + 1)

         for j in range(1, row_num):
             row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]

         triangle.append(row)

     return triangle

C++

Written by @Vipullakum007

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

     for (int row_num = 0; row_num < numRows; row_num++) {
         vector<int> row(row_num + 1, 1);

         for (int j = 1; j < row_num; j++) {
             row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j];
         }

         triangle.push_back(row);
     }

     return triangle;
 }
};

Complexity Analysis

• Time Complexity: $O(n^2)$ where n is the number of rows. This is because we are generating each element in the triangle, and there are $\frac{n(n+1)}{2}$ elements in total.
• Space Complexity: $O(n^2)$, the space required to store the triangle.

---