2. Pascal's triangle

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 as shown:

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

Constraints:

• 1 <= numRows <= 30

Approach

• Simple calculate for each row then add
• the addition would be between top left and top

$\text{row}[i][j]=\text{row}[i-1][j-1]+\text{row}[i-1][j]$

Intuitive Iterative Solution (DP / Standard Approach)

• First and last element will be 1 and for rest use the above formula
• Build the triangle row by row. Each new row is computed directly using the values from the row generated right before it.
  • Time Complexity: $\mathcal{O}(numRow{s}^2)$ — You compute every element once.
  • Space Complexity: $\mathcal{O}(numRow{s}^2)$ — Required space to store the returned triangle.

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<List<Integer>> generate(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++) {
                // First and last elements of any row are always 1
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    // Sum of two elements directly above in the previous row
                    int val = triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j);
                    row.add(val);
                }
            }
            
            triangle.add(row);
        }
 
        return triangle;
    }
}

Combinatoric Row Generation

• Instead of reading from the previous row, you can generate each row independently using the combination formula derived from $nCr$:

${\text{element}}_j={\text{element}}_{j-1}\times \frac{\text{row}-j}{j}$

• This avoids looking up previous rows and calculates each value in constant time step-by-step.
  • Time Complexity: $\mathcal{O}(numRow{s}^2)$ — Optimal minimum operations required to output all values.
  • Space Complexity: $\mathcal{O}(1)$ auxiliary space (excluding output memory).

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
 
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            long val = 1; // First element of row is always 1
            row.add((int) val);
 
            for (int j = 1; j <= i; j++) {
                // Compute next element directly: val = val * (i - j + 1) / j
                val = val * (i - j + 1) / j;
                row.add((int) val);
            }
 
            triangle.add(row);
        }
 
        return triangle;
    }
}

Why Use long?

We use long for the variable val solely to prevent integer overflow during intermediate multiplication steps.

When computing the combination value:

$\text{val}=\text{val}\times \frac{\text{row}-j+1}{j}$

We must perform the multiplication val * (i - j + 1) before dividing by j. If we divide first, we get truncation errors because integer division drops decimals.

While the final result for any element in a standard 32-bit integer array easily fits inside an int for $numRows\le 30$, the intermediate multiplication product val * (i - j + 1) can briefly exceed Integer.MAX_VALUE ($2,147,483,647$) for slightly larger rows before the division scales it back down. Using long guarantees no arithmetic overflow occurs during that intermediate step.

---

How We Derive the Math Formula

Every element in Pascal’s Triangle corresponds to a combination from probability math:

$\text{Element at row }n,\text{ column }k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$

(Note: row $n$ and column $k$ are $0$-indexed)

To find the relationship between two consecutive elements in the same row, look at the ratio between $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ and $\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$:

1. Write out the consecutive formulas:

   $\text{Current Element }(k)=\frac{n!}{k!\cdot (n-k)!}$

   $\text{Previous Element }(k-1)=\frac{n!}{(k-1)!\cdot (n-(k-1))!}=\frac{n!}{(k-1)!\cdot (n-k+1)!}$

2. Divide the Current Element by the Previous Element:

   $\frac{\text{Current}}{\text{Previous}}=\frac{\frac{n!}{k!\cdot (n-k)!}}{\frac{n!}{(k-1)!\cdot (n-k+1)!}}$

3. Simplify the fraction by canceling common terms ($n!$, factorials):

   $\frac{\text{Current}}{\text{Previous}}=\frac{(k-1)!}{k!}\times \frac{(n-k+1)!}{(n-k)!}=\frac{1}{j}\times (n-j+1)=\frac{n-j+1}{j}$

4. Rearrange to get the formula used in code:

   $\text{Current}=\text{Previous}\times \frac{n-j+1}{j}$

Easy Trick to Remember:

• Numerator: Starts at $n$ and decreases by 1 for each step across the row ($n,n-1,n-2,\dots$).

• Denominator: Counts up step-by-step ($1,2,3,\dots$).