Leetcode 118: Pascal's Triangle

Input: The input consists of a single integer, numRows, which represents the number of rows to be generated from Pascal's triangle.

Example: Input: numRows = 4

Constraints:

• 1 <= numRows <= 30

Output: The output should be a 2D array, where each row represents the corresponding row of Pascal's triangle, starting from the top.

Example: Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]

Constraints:

• The number of rows in the output should not exceed 'numRows'.

Goal: The goal is to generate Pascal's triangle row by row, where each row can be constructed by adding the elements directly above it from the previous row.

Steps:

• Start with the first row, which is always [1].

• For each subsequent row, initialize the row with 1 at the start and end.

• For each intermediate position in the row, calculate the value by adding the two numbers directly above it from the previous row.

• Repeat this process for 'numRows' rows.

Goal: The problem constraints ensure that the value of numRows will be between 1 and 30.

Steps:

• 1 <= numRows <= 30

Assumptions:

• The input value numRows is always valid and within the given constraints.

• Input: Input: numRows = 4

• Explanation: For the input numRows = 4, Pascal's triangle is generated as follows: the first row is [1], the second row is [1, 1], the third row is [1, 2, 1], and the fourth row is [1, 3, 3, 1].

• Input: Input: numRows = 2

• Explanation: For the input numRows = 2, the output will be [[1], [1, 1]].

Approach: The problem can be solved iteratively by constructing each row based on the previous one. Each new row is initialized with 1 at the boundaries, and the intermediate values are calculated by summing the two values directly above.

Observations:

• We can generate each row by leveraging the values of the previous row.

• A direct approach will involve iterating through each row and filling in the values based on the previous row.

Steps:

• Initialize the result as an empty 2D array.

• For each row from 1 to numRows, initialize the row with the appropriate number of elements (starting and ending with 1).

• For each intermediate position in the row, compute the value by adding the corresponding elements from the previous row.

• Return the resulting 2D array after generating all rows.

Empty Inputs:

• If numRows is 1, the output will just be [[1]].

Large Inputs:

• The solution should handle up to 30 rows efficiently.

Special Values:

• For numRows = 1, the output is [[1]].

Constraints:

• The input will always satisfy 1 <= numRows <= 30.

vector<vector<int>> generate(int numRows) {
      vector<vector<int>> r(numRows);

    for (int i = 0; i < numRows; i++) {
        r[i].resize(i + 1);
        r[i][0] = r[i][i] = 1;
  
        for (int j = 1; j < i; j++)
            r[i][j] = r[i - 1][j - 1] + r[i - 1][j];
    }
    
    return r;      
}

1 : Function Declaration

vector<vector<int>> generate(int numRows) {

Declare a function to generate Pascal's Triangle for a given number of rows.

2 : Vector Initialization

      vector<vector<int>> r(numRows);

Initialize a 2D vector to store the rows of Pascal's Triangle.

3 : Outer Loop

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

Iterate over each row to populate Pascal's Triangle.

4 : Row Resize

        r[i].resize(i + 1);

Resize the current row to accommodate the required number of elements.

5 : Row Boundaries

        r[i][0] = r[i][i] = 1;

Set the first and last elements of the row to 1, as they are boundaries in Pascal's Triangle.

6 : Inner Loop

        for (int j = 1; j < i; j++)

Iterate over the internal elements of the current row.

7 : Dynamic Calculation

            r[i][j] = r[i - 1][j - 1] + r[i - 1][j];

Compute each internal element as the sum of two elements directly above it in the triangle.

8 : Return Statement

    return r;

Return the completed Pascal's Triangle as a 2D vector.

Best Case: O(numRows^2)

Average Case: O(numRows^2)

Worst Case: O(numRows^2)

Description: The time complexity is O(numRows^2) because we process each element in the triangle once.

Best Case: O(numRows^2)

Worst Case: O(numRows^2)

Description: The space complexity is O(numRows^2) because the result contains a 2D array of size numRows x numRows in the worst case.

Leetcode 118: Pascal's Triangle

Solution to LeetCode 118: Pascal's Triangle Problem

Explore →