Pascal Triangle

JavaView on GFG

Time: O(n^2)

Space: O(n)

Intuition

Generate Pascal triangle up to n rows. Each element = sum of two above.

Algorithm

1row[0] = row[end] = 1. For i in 1..end-1: row[i] = prevRow[i-1] + prevRow[i].

Common Pitfalls

•Same as LC 118. Build row by row. Each row has one more element than previous.

Pascal Triangle.java

Java

// Approach: Each row: first and last are 1, middle[j] = prev[j-1] + prev[j]. Build row by row.
// Time: O(n^2) Space: O(n)
import java.util.*;

class Solution {

    ArrayList<Integer> nthRowOfPascalTriangle(int n) {
        // Convert to 0-based index (original rows are 1-based)
        n -= 1;

        ArrayList<Integer> row = new ArrayList<>();

        // Initialize the row with 1s
        for (int i = 0; i <= n; i++)
            row.add(1);

        // Build the row in-place
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--)
                row.set(j, row.get(j) + row.get(j - 1));
        }

        return row;
    }
}

Was this solution helpful?