Pascals Triangle (Part 2) Uber Python Interview Question

Hopefully, you've already solved Pascal's Triangle(part 1) – where we generated the first n rows of the triangle. Now, let’s put a twist on that problem for part 2.

Imagine you are still working with Pascal's Triangle, but instead of generating multiple rows, you're only interested in a specific one. Given the index of a row, can you compute that row directly, without generating the entire triangle?

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

For example, when , you should return , since the second row (index 1) of Pascal's triangle is (refer to the image above).

When , you should return , because the fourth row (index 3) of Pascal's triangle is (refer to the image above).

Recursive Approach

The problem says each number is calculated by adding the two numbers directly above it. That’s exactly what we are going to do! To make sure we identify which numbers are directly above, let’s visualize Pascal's Triangle as a right triangle, just like we did in the first part of this question. Here's an example of how we can visualize it as a right triangle:

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.

For each number in the current row, we use the two numbers directly above it. But what if those values aren’t available? We recursively calculate the two numbers directly above them, and keep doing this until we reach the base case.

Here is the code:

Improved Recursive Approach (Dynamic Programming)

Please refer to the right triangle we built earlier:

Can you see the two arrows pointing to the number in the second row(remember, we’re counting rows starting from )? That’s because it’s needed to calculate both of the s in the fourth row. We still have to calculate the value of in a similar way, by using the numbers directly above it ( and ).

Previously, we were doing this calculation twice — once for each in the fourth row — even though the value of remains the same. Instead of recalculating the same value multiple times, we can store (or 'cache') the value once it’s computed and reuse it whenever needed. This is where dynamic programming comes in — specifically, memoization — which optimizes the recursive solution by caching previously computed results and using them to avoid redundant calculations.

This approach significantly improves efficiency and helps avoid recalculating the same subproblems multiple times.

More on Dynamic Programming.

Here is the code:

Iterative Approach (Storing Previous Row)

In this approach, we start from the base case, which is the th row: . We then calculate each subsequent row by using the values from the previous row, as the new row's values are determined by the ones directly above it.

The key here is that we don't need to store all rows, only the previous one, to compute the current one. Once the current row is computed, we set it as the previous row for the next iteration. This allows us to build the Pascal's Triangle iteratively without using excessive memory.

Here is the code: