Pascal's Triangle

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

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:

Input: numRows = 5

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

Input: numRows = 1

Output: [[1]]

Input: numRows = 3

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

Constraints

1 ≤ numRows ≤ 30

Editorial

Intuition:

Pascal's triangle is built by starting with a 1 at the top. Each number below is the sum of the two numbers directly above it. This property allows us to generate each row from the previous row.

Approach:

Initialize an empty list to store the rows of the triangle.
For each row index i from 0 to numRows-1:
- Create a new row of size i+1 with all elements initially set to 1.
- For each inner element (from index 1 to i-1), update it to be the sum of the two elements from the previous row at indices j-1 and j.
- Add the completed row to the triangle.
Format the triangle: convert each row to a string in the form [e1, e2, ...] with elements separated by comma and a space.
Join all row strings with a single space and print the result without any extra spaces or newlines.

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    void printTriangle(int numRows) {
        vector<vector<int>> triangle;
        for (int i = 0; i < numRows; i++) {
            vector<int> row(i+1, 1);
            for (int j = 1; j < i; j++) {
                row[j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
            triangle.push_back(row);
        }
        for (int i = 0; i < triangle.size(); i++) {
            cout << "[";
            for (int j = 0; j < triangle[i].size(); j++) {
                if (j > 0) cout << ", ";
                cout << triangle[i][j];
            }
            cout << "]";
            if (i != triangle.size() - 1) cout << " ";
        }
    }
};
import java.util.*;

class Solution {
    public void printTriangle(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(triangle.get(i-1).get(j-1) + triangle.get(i-1).get(j));
                }
            }
            triangle.add(row);
        }
        for (int i = 0; i < triangle.size(); i++) {
            System.out.print("[");
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (j > 0) System.out.print(", ");
                System.out.print(triangle.get(i).get(j));
            }
            System.out.print("]");
            if (i != triangle.size() - 1) System.out.print(" ");
        }
    }
}
class Solution:
    def print_triangle(self, numRows):
        triangle = []
        for i in range(numRows):
            row = [1] * (i+1)
            for j in range(1, i):
                row[j] = triangle[i-1][j-1] + triangle[i-1][j]
            triangle.append(row)
        for i, row in enumerate(triangle):
            print("[" + ", ".join(map(str, row)) + "]", end="")
            if i != len(triangle)-1:
                print(" ", end="")
class Solution {
    printTriangle(numRows) {
        let triangle = [];
        for (let i = 0; i < numRows; i++) {
            let row = new Array(i+1).fill(1);
            for (let j = 1; j < i; j++) {
                row[j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
            triangle.push(row);
        }
        for (let i = 0; i < triangle.length; i++) {
            process.stdout.write("[");
            for (let j = 0; j < triangle[i].length; j++) {
                if (j > 0) process.stdout.write(", ");
                process.stdout.write(triangle[i][j].toString());
            }
            process.stdout.write("]");
            if (i !== triangle.length - 1) process.stdout.write(" ");
        }
    }
}

Complexity Analysis:

Time Complexity: O(numRows²) because we generate each element of the triangle exactly once. The total number of elements is numRows*(numRows+1)/2.

Space Complexity: O(numRows²) to store the triangle.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories