Pascal's Triangle

The output looks like mathematics. The interview task is simpler: build each row from the row you already have.

For the Pascal's Triangle solution, keep the completed rows in triangle. For every new row, place 1 at both ends and compute each interior value from two adjacent values in the previous row.

Although this problem appears under a Two Pointers category, it does not use the coordinated pointer movement that defines two-pointer problems. Its natural pattern is iterative dynamic programming: preserve prior state, apply a recurrence, and build the result forward.

Read the output contract first

The input is an integer numRows satisfying:

1 <= numRows <= 30

You must return the first numRows rows, in order, as a nested list. The first row is always [1], and every following row contains one more value than the previous row.

For numRows = 5, the required shape is:

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

The task is to return this data structure. It is not asking you to print a centered triangle, calculate only one requested row, or return the largest value.

That contract immediately gives us two obligations:

1. Preserve every completed row because the final answer contains all of them.
2. Construct each new row with exactly one more entry than the row before it.

See the recurrence, not the picture

The visual triangle is useful, but the rule underneath it is what drives the algorithm:

• Every row begins with 1.
• Every row ends with 1.
• Each interior value is the sum of two adjacent values in the previous row.

Suppose the previous row is:

[1, 2, 1]

The next row has boundary values 1 and 1. Its interior values come from adjacent pairs:

1 + 2 = 3
2 + 1 = 3

So the next row is:

[1, 3, 3, 1]

The previous row is the only state required to calculate the next row. However, it is not the only state we must store: the output contract requires all rows, so triangle retains the complete history.

This is a small but useful dynamic-programming shape:

Reuse the completed previous state instead of recalculating values independently.

Two indices may appear in the inner loop, but that does not make this a two-pointer algorithm. In a true two-pointer solution, pointers usually move through a search space according to an invariant, such as narrowing a range or partitioning an array. Here, j simply visits the interior positions of a row. The important dependency is between adjacent values in the previous row.

Start with the simple baseline

A first approach might calculate every entry independently using a binomial-coefficient formula. That can work, but it introduces arithmetic that the output structure does not require.

Another tempting approach is recursive: define a value in terms of values above it, then recursively calculate those values. Without careful reuse, the same subproblems are recalculated many times. Even with memoization, the recursive structure adds machinery that is unnecessary for this contract.

The iterative recurrence is the better interview choice because it matches the definition directly:

• Build row 0.
• Use row 0 to build row 1.
• Use row 1 to build row 2.
• Continue until the requested number of rows exists.

For a small maximum input, clarity matters more than formula-heavy cleverness. The code should make the dependency visible.

Derive the row-building algorithm

Use a zero-based row index i.

A row at index i has length i + 1. For example:

Row index i	Row length	Row
0	1	[1]
1	2	[1, 1]
2	3	[1, 2, 1]
3	4	[1, 3, 3, 1]

For each row:

1. Create a list containing i + 1 values.

2. Set the first and last positions to 1.

3. Fill the interior positions from 1 through i - 1.

4. For each interior position j, use:

   previous_row[j - 1] + previous_row[j]
   

5. Append the completed row to triangle.

The index range is the part most likely to go wrong. A row of length i + 1 has:

• First position: 0
• Last position: i
• Interior positions: 1 through i - 1

The boundaries do not come from the previous row. They are defined directly as 1.

Prove the invariant before coding

A useful loop invariant is:

Before building row i, triangle contains exactly the first i rows in order. If i > 0, its last row is the complete row immediately above the row being built.

This gives us a clean correctness argument.

Initialization

Before the first iteration, i = 0 and triangle is empty. It contains exactly the first zero rows, so the invariant holds.

Preservation

Assume the invariant holds before building row i.

The new row has length i + 1.

• Its first value is 1, which is correct for every row.

• Its last value is 1, which is also correct.

• For every interior index j, the algorithm assigns:

  previous_row[j - 1] + previous_row[j]
  

  That is exactly the rule defining an interior Pascal's Triangle value.

Therefore, the constructed row is correct. Appending it means triangle now contains the first i + 1 rows, so the invariant continues to hold.

Termination

After numRows iterations, the result contains exactly the first numRows rows in order. That is the required output.

The invariant is more than formal decoration here. It protects against the common off-by-one mistake: trying to read a nonexistent neighbor when j reaches the first or last position.

Implement Pascal's Triangle in Python

This Python implementation builds each row independently, which avoids accidentally sharing one mutable list between multiple rows.

from typing import List


class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        triangle = []

        for i in range(numRows):
            row = [1] * (i + 1)

            for j in range(1, i):
                previous_row = triangle[i - 1]
                row[j] = previous_row[j - 1] + previous_row[j]

            triangle.append(row)

        return triangle

The variables each have a specific job:

• triangle stores the complete output.
• i identifies the row being constructed.
• row is the new row.
• j visits only interior positions.
• previous_row provides the two values needed for each interior sum.

For i = 0, the row is [1], and the inner loop does not run. For i = 1, the row is [1, 1], and again there are no interior positions. That means the implementation handles the first two rows naturally without a separate prepopulation branch.

The expression [1] * (i + 1) creates a new list for each iteration. That detail matters. Do not create one row once and repeatedly append or mutate it as if it were a fresh row each time. Every entry in triangle must remain an independent list.

A slightly different implementation can construct a row by appending its first boundary, then the interior sums, then its final boundary. The important design is the same: boundaries are fixed, and the middle comes from the previous row.

Dry-run the state on five rows

Tracing the state makes the index ranges concrete.

Row index 0

Create a row of length 1:

row = [1]

There are no interior positions. Append it:

triangle = [[1]]

Row index 1

Create a row of length 2:

row = [1, 1]

The inner range is range(1, 1), so it is empty. Append:

triangle = [
    [1],
    [1, 1],
]

Row index 2

Start with:

row = [1, 1, 1]
previous_row = [1, 1]

The only interior index is j = 1:

row[1] = previous_row[0] + previous_row[1]
       = 1 + 1
       = 2

Now:

[1, 2, 1]

Row index 3

Start with:

row = [1, 1, 1, 1]
previous_row = [1, 2, 1]

There are two interior positions:

row[1] = 1 + 2 = 3
row[2] = 2 + 1 = 3

The completed row is:

[1, 3, 3, 1]

Row index 4

Start with:

row = [1, 1, 1, 1, 1]
previous_row = [1, 3, 3, 1]

Compute the three interior values:

row[1] = 1 + 3 = 4
row[2] = 3 + 3 = 6
row[3] = 3 + 1 = 4

The completed row is:

[1, 4, 6, 4, 1]

The result now contains five rows, and each row is one element longer than the preceding row.

When debugging a nested-list result, inspect this intermediate state. If a row has the wrong length, check i + 1. If an edge is wrong, check the boundary initialization. If an interior value is wrong, print j, previous_row[j - 1], and previous_row[j]. Read the error, trace the state, fix the assumption.

Complexity and edge cases

For numRows rows, the total number of output values is:

1 + 2 + 3 + ... + numRows

That sum grows quadratically, so generating the required output takes:

Time: O(numRows²)

This is also a lower bound for any solution that must explicitly return every value. The algorithm has to create and populate all of them.

The returned triangle occupies:

Output space: O(numRows²)

The current row uses up to O(numRows) working space, but the stored output dominates the asymptotic space usage:

Auxiliary working space: O(numRows)
Total space including the returned output: O(numRows²)

Do not describe this solution as constant-space simply because it uses loops instead of recursion. The result itself is a two-dimensional collection whose size grows quadratically.

Important boundary cases:

• numRows = 1 returns:

  [[1]]
  

• numRows = 2 returns:

  [[1], [1, 1]]
  

• The stated contract excludes numRows = 0, so zero-row behavior is not a required case to design around.

• The maximum stated input is 30, which is small enough for this direct row-building approach and ordinary Python integer arithmetic.

The interview takeaway

When a new output row is defined from adjacent values in the completed previous row, recognize the shape:

1. Name the previous state.
2. Preserve the full output if the contract asks for every state.
3. Set the boundary values explicitly.
4. Fill the interior from the recurrence.
5. State the invariant before writing the loops.

That is the reusable Pascal's Triangle solution pattern. Do not classify a problem by the category label alone, and do not call every pair of indices “two pointers.” Here, the key signal is dependency on prior state.

Your next move should be to re-implement the solution without looking at the code. Say out loud why the interior range is 1 through i - 1, why the row length is i + 1, and why the previous row remains available. The durable skill is not memorizing a triangle snippet. It is recognizing a local recurrence, turning it into state and loops, and proving that the boundaries and interior values cannot drift apart.