Domain 1EasyCORE

Pascal's Triangle

The problem asks us to generate the first `numRows` of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. The input is an integer `numRows`, which specifies how many rows of the triangle we need to generate. The output should be a list of lists, where each inner list represents a row in Pascal's triangle.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

118. Pascal’s Triangle

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 55.4%


Problem Breakdown

The problem asks us to generate the first numRows of Pascal’s triangle. In Pascal’s triangle, each number is the sum of the two numbers directly above it. The input is an integer numRows, which specifies how many rows of the triangle we need to generate. The output should be a list of lists, where each inner list represents a row in Pascal’s triangle.

Inputs:

  • An integer numRows (1 <= numRows <= 30)

Outputs:

  • A list of lists containing integers representing the first numRows of Pascal’s triangle.

Implicit Constraints/Edge Cases:

  • The smallest input is numRows = 1, which should return [[1]].
  • The largest input is numRows = 30, which requires generating a relatively large triangle but still manageable within the constraints.
  • There are no negative numbers or duplicates to consider.

Intuition

A brute-force approach would involve manually calculating each element of Pascal’s triangle by iterating through previous rows and summing adjacent elements. However, this approach is inefficient in terms of both time and space complexity because it involves repeated calculations and storing intermediate results unnecessarily.

The key insight is that each row in Pascal’s triangle can be generated based on the previous row using a simple formula: each element (except the first and last) is the sum of the two elements directly above it from the previous row. This allows us to build the triangle iteratively, which is both time-efficient and space-efficient.

Approach

  1. Initialize the Result List: Start with an empty list result that will store all rows of Pascal’s triangle.
  2. Iterate Over Rows: Use a loop to generate each row from 0 to numRows - 1.
  3. Generate Each Row:
    • For the first row (row index 0), append [1] to result.
    • For subsequent rows, initialize a new list current_row with the first element as 1.
    • Use another loop to fill in the middle elements of current_row by summing adjacent elements from the previous row.
    • Append 1 as the last element of current_row.
  4. Append Current Row: Add current_row to result.
  5. Return Result: After all rows are generated, return the result.

Complexity Analysis

  • Time Complexity: O(numRows^2). This is because we generate each row in linear time relative to its length, and there are numRows rows.
  • Space Complexity: O(numRows^2). We store all elements of Pascal’s triangle in the result list.

Solution

def generate(numRows):
    result = []
    
    for i in range(numRows):
        current_row = [1] * (i + 1)
        
        if i > 0:
            for j in range(1, i):
                current_row[j] = result[i - 1][j - 1] + result[i - 1][j]
        
        result.append(current_row)
    
    return result

Edge Cases Handled

  • numRows = 1: The function correctly returns [[1]].
  • numRows = 2: The function correctly returns [[1], [1, 1]].
  • numRows = 30: The function efficiently generates the first 30 rows of Pascal’s triangle without running into performance issues.