118. Pascal's Triangle

Easy

Problem Description

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.

Examples

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

Example 2:
Input: numRows = 1
Output: [[1]]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def generate(numRows: int) -> List[List[int]]:
    # Initialize triangle with first row
    triangle = [[1]]
    
    for i in range(1, numRows):
        # Previous row
        prev_row = triangle[-1]
        # Current row starts with 1
        current_row = [1]
        
        # Calculate middle elements
        for j in range(1, i):
            current_row.append(prev_row[j-1] + prev_row[j])
        
        # Add final 1
        current_row.append(1)
        
        # Add row to triangle
        triangle.append(current_row)
    
    return triangle

Java Solution


class Solution {
    public List> generate(int numRows) {
        List> triangle = new ArrayList<>();
        
        // First row is always [1]
        triangle.add(Arrays.asList(1));
        
        for (int i = 1; i < numRows; i++) {
            List prev_row = triangle.get(i - 1);
            List current_row = new ArrayList<>();
            
            // First element is always 1
            current_row.add(1);
            
            // Calculate middle elements
            for (int j = 1; j < i; j++) {
                current_row.add(prev_row.get(j-1) + prev_row.get(j));
            }
            
            // Last element is always 1
            current_row.add(1);
            
            triangle.add(current_row);
        }
        
        return triangle;
    }
}

C++ Solution


class Solution {
public:
    vector> generate(int numRows) {
        vector> triangle;
        
        // First row is always [1]
        triangle.push_back({1});
        
        for (int i = 1; i < numRows; i++) {
            vector& prev_row = triangle.back();
            vector current_row = {1};  // First element
            
            // Calculate middle elements
            for (int j = 1; j < i; j++) {
                current_row.push_back(prev_row[j-1] + prev_row[j]);
            }
            
            // Last element is always 1
            current_row.push_back(1);
            
            triangle.push_back(current_row);
        }
        
        return triangle;
    }
};

JavaScript Solution


/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    // Initialize triangle with first row
    const triangle = [[1]];
    
    for (let i = 1; i < numRows; i++) {
        const prev_row = triangle[i - 1];
        const current_row = [1];  // First element
        
        // Calculate middle elements
        for (let j = 1; j < i; j++) {
            current_row.push(prev_row[j-1] + prev_row[j]);
        }
        
        // Last element is always 1
        current_row.push(1);
        
        triangle.push(current_row);
    }
    
    return triangle;
};

C# Solution


public class Solution {
    public IList> Generate(int numRows) {
        IList> triangle = new List>();
        
        // First row is always [1]
        triangle.Add(new List { 1 });
        
        for (int i = 1; i < numRows; i++) {
            IList prev_row = triangle[i - 1];
            IList current_row = new List();
            
            // First element is always 1
            current_row.Add(1);
            
            // Calculate middle elements
            for (int j = 1; j < i; j++) {
                current_row.Add(prev_row[j-1] + prev_row[j]);
            }
            
            // Last element is always 1
            current_row.Add(1);
            
            triangle.Add(current_row);
        }
        
        return triangle;
    }
}

Complexity Analysis

Solution Explanation

This solution builds Pascal's Triangle row by row:

Key points: