Pascals Triangle

XXX. Pascal's Triangle

Dynamic Programming

Problem Statement:

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

In Pascal's Triangle, each number is the sum of the two numbers directly above it.

Algorithm:

1. Initialize a result list to store all rows of Pascal's Triangle.
2. Add the first row, which always contains a single 1.
3. For each subsequent row:
   • Start the row with 1.
   • Compute the intermediate values by summing adjacent values from the previous row.
   • End the row with 1.
4. Append the completed row to the result list.
5. Return the result list after generating all rows.

Complexity:

Time Complexity: O(numRows²), as each row has a number of elements proportional to its index.
Space Complexity: O(numRows²), as we store all rows in the result list.

Java Implementation:

import java.util.*;

class Solution {
    public List> generate(int numRows) {
        List> result = new ArrayList<>(); // Stores all rows of Pascal's Triangle

        if (numRows == 0) return result; // Return empty list for 0 rows

        // Add the first row
        List first = new ArrayList<>();
        first.add(1);
        result.add(first);

        // Generate each row
        for (int rows = 1; rows < numRows; rows++) {
            List row = new ArrayList<>(); // Current row
            row.add(1); // Start the row with 1

            List prev = result.get(rows - 1); // Previous row

            // Compute intermediate values
            for (int i = 1; i < prev.size(); i++) {
                row.add(prev.get(i - 1) + prev.get(i)); // Sum of adjacent values
            }

            row.add(1); // End the row with 1
            result.add(row); // Add the row to the result
        }

        return result;
    }
}

Python Implementation:

def generate(numRows):
    result = [] # Stores all rows of Pascal's Triangle

    if numRows == 0:
        return result # Return empty list for 0 rows

    # Add the first row
    result.append([1])

    # Generate each row
    for rows in range(1, numRows):
        row = [1] # Start the row with 1
        prev = result[rows - 1] # Previous row

        # Compute intermediate values
        for i in range(1, len(prev)):
            row.append(prev[i - 1] + prev[i]) # Sum of adjacent values

        row.append(1) # End the row with 1
        result.append(row) # Add the row to the result

    return result

C++ Implementation:

#include 
using namespace std;

vector> generate(int numRows) {
    vector> result; // Stores all rows of Pascal's Triangle

    if (numRows == 0)
        return result; // Return empty list for 0 rows

    // Add the first row
    result.push_back({1});

    // Generate each row
    for (int rows = 1; rows < numRows; rows++) {
        vector row = {1}; // Start the row with 1
        vector prev = result[rows - 1]; // Previous row

        // Compute intermediate values
        for (int i = 1; i < prev.size(); i++) {
            row.push_back(prev[i - 1] + prev[i]); // Sum of adjacent values
        }

        row.push_back(1); // End the row with 1
        result.push_back(row); // Add the row to the result
    }

    return result;
}