algoadvance

Leetcode 118. Pascal’s Triangle

Problem Statement

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:

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

Clarifying Questions

1. Q: Is numRows guaranteed to be a positive integer?
   • A: Yes, numRows is guaranteed to be a positive integer.
2. Q: What is the maximum value for numRows?
   • A: The constraints indicate numRows is reasonably small, usually up to 30 in typical interview constraints.
3. Q: Should the solution handle special cases, such as numRows = 1?
   • A: Yes, the solution should handle cases where numRows is as small as 1.

Strategy

1. Initialization:
   • Create a 2D vector to store the result.
2. Iterate to Generate Rows:
   • Use a loop to generate each row from 0 to numRows-1.
   • Initialize each row with 1s, since the first and last elements of each row are always 1.
3. Fill Middle Values:
   • For each row from the third one onward, calculate the inner elements as the sum of the two elements directly above it from the previous row.
4. Return Result:
   • Return the 2D vector containing all the rows of Pascal’s triangle.

Time Complexity

• Time Complexity: (O(numRows^2))
  • This is because generating each element in the triangle involves iterating through each row and each element within the row. The total number of elements in Pascal’s triangle up to n rows is ( \frac{n(n + 1)}{2} ), which is (O(numRows^2)).

Code

#include <vector>
using namespace std;

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

    for (int i = 0; i < numRows; ++i) {
        vector<int> row(i + 1, 1); // initialize row with 1s
        
        for (int j = 1; j < i; ++j) {
            row[j] = pascalTriangle[i - 1][j - 1] + pascalTriangle[i - 1][j];
        }
        
        pascalTriangle.push_back(row);
    }
    
    return pascalTriangle;
}

This implementation initializes each row with 1s and uses a nested loop to fill in the middle elements correctly based on the values from the previous row. It ensures that the output is in the correct format representing Pascal’s triangle up to the given number of rows.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?