Pascal's Triangle - Practice Coding Problems

Pascal's Triangle - Problem

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. The triangle starts with 1 at the top, and each row begins and ends with 1.

Example: For numRows = 5, the triangle looks like:

Input & Output

Example 1 — Basic Triangle

$ Input: numRows = 5

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

💡 Note: First 5 rows of Pascal's triangle. Row 0 is [1], Row 1 is [1,1], Row 2 is [1,2,1] where 2=1+1, Row 3 is [1,3,3,1] where 3=1+2, and Row 4 is [1,4,6,4,1] where 4=1+3 and 6=3+3.

Example 2 — Small Triangle

$ Input: numRows = 1

› Output: [[1]]

💡 Note: Only the top of the triangle with just one element: 1

Example 3 — Two Rows

$ Input: numRows = 2

› Output: [[1],[1,1]]

💡 Note: First two rows: the top [1] and second row [1,1]

Constraints

1 ≤ numRows ≤ 30

Visualization

Tap to expand

Understanding the Visualization

Input

numRows = 5 (we want first 5 rows)

Process

Build triangle where each number = sum of two above

Output

2D array with 5 rows of Pascal's triangle

Key Takeaway

🎯 Key Insight: Pascal's triangle follows a simple pattern where each interior element is the sum of the two elements directly above it, making it perfect for dynamic programming.

Asked in

🍎 Apple 15 Ⓜ Microsoft 12 G Google 8 A Amazon 6

The key insight is that each element in Pascal's triangle equals the sum of the two elements directly above it. Best approach is to build the triangle row by row, using the previous row to compute the current row. Time: O(n²), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Space-Optimized Construction	O(n²)	O(n²)	Build the triangle row by row with optimal memory usage
Row by Row Construction	O(n²)	O(n²)	Build each row by computing each element from the previous row

Space-Optimized Construction — Algorithm Steps

Step 1: Handle edge case for numRows = 0
Step 2: Build each row incrementally
Step 3: Use previous row values to compute current row
Step 4: Add completed row to triangle

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Row

Begin each row with 1

Add Middle

Sum adjacent pairs from previous row

End Row

Add final 1 to complete row

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int numRows, int* returnSize, int** returnColumnSizes) {
    *returnSize = numRows;
    if (numRows == 0) {
        *returnColumnSizes = NULL;
        return NULL;
    }
    
    int** triangle = (int**)malloc(numRows * sizeof(int*));
    *returnColumnSizes = (int*)malloc(numRows * sizeof(int));
    
    for (int i = 0; i < numRows; i++) {
        (*returnColumnSizes)[i] = i + 1;
        triangle[i] = (int*)malloc((i + 1) * sizeof(int));
        
        triangle[i][0] = 1;
        
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
        
        if (i > 0) {
            triangle[i][i] = 1;
        }
    }
    
    return triangle;
}

int main() {
    int numRows;
    scanf("%d", &numRows);
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(numRows, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Still need to generate all n(n+1)/2 elements in the triangle

⚠ Quadratic Growth

Space Complexity

O(n²)

Must store the entire triangle result

⚠ Quadratic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Space-Optimized Construction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler