Back to questions

Given an integer , 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:

For , you should return .

For , you should return .

Imagine building a triangle where every row starts and ends with a . The magic happens in the middle. How? Every number inside the row is simply the sum of the two numbers directly above it from the previous row.

Let's make this even simpler by thinking of Pascal's Triangle as a right triangle while we build it:

In this orientation, when constructing each row, you can take the number directly above and the number to the left of it (still above) to compute the new value.

We'll use an iterative approach to build each row of Pascal's Triangle.

- Start with the first row .
- For each subsequent row, start and end with .
- Fill in the middle elements by summing the appropriate elements from the previous row.
- Append each completed row to our main triangle list.

Here's the iterative solution:

Most of the time, interviewers may ask you to solve a problem using multiple approaches or at least mention an alternative.

Here's a recursive solution:

In case you aren't familiar with recursion, it is a way of solving a problem by breaking it down into smaller subproblems until a base case is reached. For the base case is the first row .

- Base Case: If is , return
- Recursive Case: Call the function with to generate the smaller triangle.

The recursive solution can lead to higher memory usage due to the function call stack. Each recursive call adds a new frame to the stack, consuming additional memory.

In contrast, the iterative approach uses a loop to build the triangle, which operates in constant stack space. This makes the iterative approach more memory efficient.