Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Pascal's Triangle

EASYProblemSolveExternal Links

Description

Given an integer numRows, generate and return the first numRows rows of Pascal's Triangle.

In Pascal's Triangle:

  • The triangle starts with a single 1 at the top (row 0).
  • Each row begins and ends with 1.
  • Every other element in a row is computed by adding the two elements directly above it from the previous row.

Return the result as a list of lists, where the i-th list contains the elements of the i-th row (0-indexed).

Examples

Example 1

Input: numRows = 5

Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Explanation:

  • Row 0: [1] — the first row is always just [1].
  • Row 1: [1, 1] — starts and ends with 1, no middle elements.
  • Row 2: [1, 2, 1] — the middle element 2 = 1 + 1 (sum of the two elements above it from row 1).
  • Row 3: [1, 3, 3, 1] — element 3 = 1 + 2 and element 3 = 2 + 1 (from row 2).
  • Row 4: [1, 4, 6, 4, 1] — element 4 = 1 + 3, element 6 = 3 + 3, element 4 = 3 + 1 (from row 3).

Example 2

Input: numRows = 1

Output: [[1]]

Explanation: With only 1 row requested, we return just the first row, which is always [1].

Example 3

Input: numRows = 3

Output: [[1], [1, 1], [1, 2, 1]]

Explanation:

  • Row 0: [1]
  • Row 1: [1, 1]
  • Row 2: [1, 2, 1] — the middle 2 is the sum of both 1s from row 1.

Constraints

  • 1 ≤ numRows ≤ 30

Editorial

Brute Force

Intuition

Each element in Pascal's Triangle has a direct mathematical formula. The element at row r and column c (0-indexed) is the binomial coefficient C(r, c) = r! / (c! × (r - c)!).

So the most straightforward approach is: for each row r from 0 to numRows - 1, and for each column c from 0 to r, compute C(r, c) using the factorial formula and place it in the result.

Think of it like this: instead of building the triangle by adding numbers from the previous row, you independently calculate every single number from scratch using the mathematical formula. It is like computing each cell of a spreadsheet using a complex formula rather than referencing neighboring cells that are already computed.

Step-by-Step Explanation

Let's trace through numRows = 5:

Step 1: Row 0 — compute C(0, 0) = 0! / (0! × 0!) = 1. Row = [1].

Step 2: Row 1 — compute C(1, 0) = 1 and C(1, 1) = 1. Row = [1, 1].

Step 3: Row 2 — compute C(2, 0) = 1, C(2, 1) = 2! / (1! × 1!) = 2, C(2, 2) = 1. Row = [1, 2, 1].

Step 4: Row 3 — compute C(3, 0) = 1, C(3, 1) = 3! / (1! × 2!) = 3, C(3, 2) = 3! / (2! × 1!) = 3, C(3, 3) = 1. Row = [1, 3, 3, 1].

Step 5: Row 4 — compute C(4, 0) = 1, C(4, 1) = 4, C(4, 2) = 4! / (2! × 2!) = 6, C(4, 3) = 4, C(4, 4) = 1. Row = [1, 4, 6, 4, 1].

For each C(r, c), we compute three factorials. Computing r! requires r multiplications, so each element costs O(r) work. Row r has (r + 1) elements, giving O(r²) per row. Summing across all rows: O(n³) total.

Result: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Brute Force — Computing Each Element with nCr Formula — Watch how each element is independently calculated using the binomial coefficient formula C(r, c). Each cell requires computing factorials from scratch.

Algorithm

  1. Create a helper function nCr(n, r) that computes the binomial coefficient C(n, r) = n! / (r! × (n - r)!).
  2. Initialize an empty result list.
  3. For each row index r from 0 to numRows - 1:
    a. Create an empty row list.
    b. For each column index c from 0 to r:
    • Compute nCr(r, c) and add it to the row.
      c. Add the row to the result.
  4. Return the result.

Code

#include <vector>
using namespace std;

class Solution {
public:
    // Compute n! / (r! * (n-r)!)
    long long nCr(int n, int r) {
        long long num = 1, den = 1;
        for (int i = 0; i < r; i++) {
            num *= (n - i);
            den *= (i + 1);
        }
        return num / den;
    }
    
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        
        for (int r = 0; r < numRows; r++) {
            vector<int> row;
            for (int c = 0; c <= r; c++) {
                row.push_back((int)nCr(r, c));
            }
            result.push_back(row);
        }
        
        return result;
    }
};
class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        def nCr(n: int, r: int) -> int:
            num, den = 1, 1
            for i in range(r):
                num *= (n - i)
                den *= (i + 1)
            return num // den
        
        result = []
        for r in range(numRows):
            row = []
            for c in range(r + 1):
                row.append(nCr(r, c))
            result.append(row)
        
        return result
import java.util.ArrayList;
import java.util.List;

class Solution {
    private long nCr(int n, int r) {
        long num = 1, den = 1;
        for (int i = 0; i < r; i++) {
            num *= (n - i);
            den *= (i + 1);
        }
        return num / den;
    }
    
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        
        for (int r = 0; r < numRows; r++) {
            List<Integer> row = new ArrayList<>();
            for (int c = 0; c <= r; c++) {
                row.add((int) nCr(r, c));
            }
            result.add(row);
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n³)

For each of the n rows, row r has r + 1 elements. Computing each element using the nCr function takes O(r) time (a loop of r multiplications). So the total work is:

Σ (r=0 to n-1) of (r+1) × r = Σ r² ≈ n³/3 = O(n³).

Space Complexity: O(1) auxiliary

Beyond the output (which stores all n² / 2 elements), we only use a few integer variables for the nCr computation. No extra data structures are needed.

Why This Approach Is Not Efficient

The brute force computes each element independently using the factorial formula. This means for every single element, we re-derive the factorial values from scratch. There is massive redundant computation — for example, C(4, 2) and C(4, 3) both compute 4!, and C(3, 1) already gave us the value 3 which is directly reusable.

More fundamentally, Pascal's Triangle has a beautiful recursive property: each element is the sum of the two elements directly above it. The element at position (r, c) equals the element at (r-1, c-1) plus the element at (r-1, c). This means once we have computed a row, the next row can be built in O(row_length) time — no factorial computation needed at all.

By exploiting this property, we can reduce the per-element cost from O(r) to O(1), bringing the total from O(n³) down to O(n²) — which is optimal since we must output n²/2 elements.

Optimal Approach - Build Each Row from the Previous Row

Intuition

Instead of computing each element from scratch with factorials, we leverage the defining property of Pascal's Triangle: every element is the sum of the two elements above it.

Imagine building a brick wall where each brick sits on top of two bricks below it, and you write on each new brick the sum of the two bricks it rests on. You only need to look at the bricks from the previous layer — you never need to go back further or pull out a calculator.

The process is simple:

  1. Start with the first row: [1].
  2. To build any subsequent row:
    • Start and end with 1.
    • For each middle position c, compute: newRow[c] = previousRow[c - 1] + previousRow[c].
  3. Repeat until you have all the requested rows.

This is both intuitive and efficient — each element takes O(1) time since we just add two numbers we already have.

Step-by-Step Explanation

Let's trace through numRows = 5:

Step 1: Create row 0: [1]. This is the base case.

  • Result: [[1]]

Step 2: Build row 1 using row 0 = [1].

  • First element: 1 (always)
  • Last element: 1 (always)
  • No middle elements (row length = 2, only first and last).
  • Row 1 = [1, 1]
  • Result: [[1], [1, 1]]

Step 3: Build row 2 using row 1 = [1, 1].

  • First element: 1
  • Middle element at c=1: prevRow[0] + prevRow[1] = 1 + 1 = 2
  • Last element: 1
  • Row 2 = [1, 2, 1]
  • Result: [[1], [1, 1], [1, 2, 1]]

Step 4: Build row 3 using row 2 = [1, 2, 1].

  • First element: 1
  • c=1: prevRow[0] + prevRow[1] = 1 + 2 = 3
  • c=2: prevRow[1] + prevRow[2] = 2 + 1 = 3
  • Last element: 1
  • Row 3 = [1, 3, 3, 1]
  • Result: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]

Step 5: Build row 4 using row 3 = [1, 3, 3, 1].

  • First element: 1
  • c=1: prevRow[0] + prevRow[1] = 1 + 3 = 4
  • c=2: prevRow[1] + prevRow[2] = 3 + 3 = 6
  • c=3: prevRow[2] + prevRow[3] = 3 + 1 = 4
  • Last element: 1
  • Row 4 = [1, 4, 6, 4, 1]

Result: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Building Pascal's Triangle Row by Row — Watch how each new row is constructed by adding adjacent pairs from the previous row. Each element (except the first and last 1s) is the sum of the two elements above it.

Algorithm

  1. Initialize the result with the first row: [[1]].
  2. For each subsequent row r from 1 to numRows - 1:
    a. Get the previous row: prevRow = result[r - 1].
    b. Create a new row starting with [1].
    c. For each column c from 1 to r - 1 (the middle elements):
    • Compute newRow[c] = prevRow[c - 1] + prevRow[c].
      d. End the row with 1.
      e. Add the new row to the result.
  3. Return the result.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        
        for (int r = 0; r < numRows; r++) {
            vector<int> row(r + 1, 1);
            
            for (int c = 1; c < r; c++) {
                row[c] = result[r - 1][c - 1] + result[r - 1][c];
            }
            
            result.push_back(row);
        }
        
        return result;
    }
};
class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        result = []
        
        for r in range(numRows):
            row = [1] * (r + 1)
            
            for c in range(1, r):
                row[c] = result[r - 1][c - 1] + result[r - 1][c]
            
            result.append(row)
        
        return result
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        
        for (int r = 0; r < numRows; r++) {
            List<Integer> row = new ArrayList<>();
            
            for (int c = 0; c <= r; c++) {
                if (c == 0 || c == r) {
                    row.add(1);
                } else {
                    row.add(result.get(r - 1).get(c - 1) 
                          + result.get(r - 1).get(c));
                }
            }
            
            result.add(row);
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

We generate n rows. Row r has r + 1 elements, and each element takes O(1) time to compute (a single addition of two previously computed values). Total elements generated: 1 + 2 + 3 + ... + n = n × (n + 1) / 2 = O(n²). Each element costs O(1), so total time is O(n²).

This is optimal — we cannot do better than O(n²) because the output itself contains O(n²) elements that must all be computed and stored.

Space Complexity: O(1) auxiliary

Beyond the output result (which stores all n²/2 elements), we only use a few loop variables. Each new row is built using values from the previous row that is already stored in the result. No additional data structures are needed.