119. Pascal's Triangle II

EasyArrayDynamic Programming
Leetcode Link

Problem Description

The task is to generate a specific row from Pascal's triangle, which is a triangular array of the binomial coefficients. Pascal's triangle is constructed such that each number in the triangle is the sum of the two numbers directly above it in the previous row. The rows of Pascal's triangle are conventionally enumerated starting with row 0 at the top (1), with each row getting progressively longer. The problem requires us not to construct the entire triangle but to return only the row at the specified index (rowIndex), which is zero-indexed.

Intuition

To arrive at the solution approach without constructing the entire Pascal's triangle, we exploit the fact that each element in a row can be calculated based on the previous row's elements. For the algorithm provided, we initialize a list, f, to contain 1s with a length of rowIndex + 1, representing the number of elements in the target row. The first and last elements in any row of Pascal's triangle are always 1.

Then we iterate through the list starting from the third row (since the first two rows are always [1] and [1, 1]), and we move backwards inside each row to calculate the new value for each position based on the previous value and the value before it (f[j] += f[j - 1]). This in-place update allows us to build the current row directly from the values of the previous row without extra space for storing the entire triangle.

The thinking process is mainly about optimizing space since we only need the final row, not the entire triangle, and building upon the knowledge of the relationship between the elements in Pascal's triangle.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

The implementation of the solution follows a bottom-up approach in calculating the values of a specific row in the Pascal's triangle. The code makes use of an array to dynamically update and calculate the row's values in-place. Here's a breakdown of the implementation:

  1. We initialize a list f with rowIndex + 1 elements, all set to 1. This represents our row in Pascal's triangle, where the first and last elements are always 1, and there are rowIndex + 1 elements in the rowIndex'th row.

  2. We then iterate from the third row (index 2) up to rowIndex inclusive, because the first two rows are always [1] and [1, 1] and do not change.

  3. For each row i, we update the values starting from the end (at position i - 1) down to 1. We do this backward so that each value uses the original value from the preceding step. We update each element f[j] by adding to it the value before it, f[j - 1] (f[j] += f[j - 1]). This effectively calculates the current element based on the two elements above it in the Pascal's triangle.

    • For example, in row 4, to calculate the value at index 2, we add the value at f[1] and f[2] from row 3. Since we move backward, the value at f[2] is still the original one from row 3.

  4. We follow this update process for all rows until we reach the desired rowIndex. By then, list f contains the correct values for that particular row in the Pascal's triangle.

  5. Finally, we return the list f as the result, which now contains the values of the rowIndex'th row of the Pascal's triangle.

This algorithm is efficient because it uses only a single list, hence the space complexity is O(n), where n is the rowIndex. The time complexity is also O(n^2), since we must compute the values for each element in the list, and the number of calculations per row grows linearly with the row index.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Let's apply the solution approach to calculate the 4th row (zero-indexed, so it is actually the 5th row in human terms) of Pascal's triangle. Recall that the 4th row index corresponds to [1, 4, 6, 4, 1] in Pascal's triangle.

We initialize f to [1, 1, 1, 1, 1] to represent the 4th row with its length being rowIndex + 1, which is 5 in this case.

Now, we iteratively update the list starting from the third row:

  • For the third row (index 2), we leave the first and last elements as 1 and update the middle one. We start from the end going backward, so f[1] (which is the second element in the array) is updated by adding the value of the first element (f[0]):

    • f[1] was 1, and f[0] is also 1, so f[1] becomes 1 + 1 = 2.

  • Now the list looks like [1, 2, 1, 1, 1].

Next, we move to the fourth row (index 3):

  • Starting from the end again, we first update f[2], which depends on f[1] and f[2] from the previous step:

    • Initially, both f[1] and f[2] are 2, so f[2] becomes 2 + 2 = 4.

  • Then we update f[1], which will be the sum of the original f[0] and f[1] from the prior step:

    • We already know that f[0] is 1 and the updated f[1] is 2, so f[1] becomes 1 + 2 = 3.

  • Now our list is [1, 3, 4, 1, 1].

Finally, for the row we're interested in (the 4th row, index 4):

  • We update f[3] similarly, which now becomes the sum of the previous f[2] and f[3]:

    • With f[2] being 4 and f[3] being 1, f[3] is updated to 4 + 1 = 5.

  • And then f[2] gets updated, this time using the new value of f[3] and the previous value of f[2]:

    • Now f[2] is updated to 3 + 4 = 7.

  • The f[1] is updated to be the sum of f[1] and f[2] from the previous set:

    • We update f[1] to 3 + 3 = 6.

  • The list now represents the 4th row and is [1, 4, 6, 4, 1].

We return [1, 4, 6, 4, 1] as the solution to the problem for the 4th row index. Each step uses the values from the previous step, and we only need to store one row at a time, ensuring that the space complexity is linear with respect to the row index given.

Solution Implementation

1class Solution:
2    def getRow(self, rowIndex: int) -> List[int]:
3        row = [1] * (rowIndex + 1)  # Initialize the row with 1s
4        # Start from the third row, since the first two rows are trivially [1] and [1, 1]
5        for i in range(2, rowIndex + 1):
6            # Move backwards to update the current row in place
7            # This is required to ensure we use the values from the previous iteration
8            # Starting at the second to last item of the row and ending at the second item
9            # since the first and the last items of the row are always 1
10            for j in range(i - 1, 0, -1):
11                # Update the value of the current cell by adding the value of the cell
12                # to the left of the current cell, which effectively calculates the binomial coefficient
13                row[j] += row[j - 1]
14        return row
15
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    // Function to return the specified row of Pascal's triangle.
6    public List<Integer> getRow(int rowIndex) {
7        // Initialize the list to hold the row values
8        List<Integer> row = new ArrayList<>();
9      
10        // Create the first row of Pascal's triangle with all elements initialized to 1 
11        for (int i = 0; i <= rowIndex; ++i) {
12            row.add(1);
13        }
14      
15        // Generate the values for the rest of the Pascal's triangle row,
16        // starting from the third row (since the first two rows are all 1s)
17        for (int i = 2; i <= rowIndex; ++i) {
18            // Move backwards to modify the row in place,
19            // calculating the sum of two elements from the previous row
20            for (int j = i - 1; j > 0; --j) {
21                // Set the current position with the sum of the two elements above it
22                row.set(j, row.get(j) + row.get(j - 1));
23            }
24        }
25      
26        // Return the completed row of Pascal's triangle
27        return row;
28    }
29}
30
1#include <vector>
2
3class Solution {
4public:
5    // Function to calculate and return the rowIndex-th row of Pascal's Triangle
6    std::vector<int> getRow(int rowIndex) {
7        // Initialize a vector with size of rowIndex+1 elements, all set to 1
8        // This will hold the current state of the row being calculated
9        std::vector<int> row(rowIndex + 1, 1);
10      
11        // Start iterating from the third row, because the first two rows are [1] and [1, 1]
12        for (int i = 2; i < rowIndex + 1; ++i) {
13            // Update the row values from the end to the beginning
14            // This is done in reverse to avoid overwriting values needed for calculation.
15            // Example: for the third iteration the row is [1, 1, 1], and this loop updates it to [1, 2, 1]
16            for (int j = i - 1; j > 0; --j) {
17                // Current element is the sum of the element above it and the element to the left of the above element
18                row[j] += row[j - 1];
19            }
20        }
21
22        // Return the fully computed row
23        return row;
24    }
25};
26
1function getRow(rowIndex: number): number[] {
2    // Initialize an array to hold the coefficients with all elements as 1
3    // which represents the first and last element of each row being 1
4    const rowCoefficients: number[] = Array(rowIndex + 1).fill(1);
5
6    // Start from the third row since the first two rows are always [1] and [1, 1]
7    for (let i = 2; i < rowIndex + 1; ++i) {
8        // Update coefficients from the end to avoid overwriting elements
9        // that are yet to be updated
10        for (let j = i - 1; j > 0; --j) {
11            // Pascal's triangle property: each number is the sum of the two numbers above it
12            rowCoefficients[j] += rowCoefficients[j - 1];
13        }
14    }
15
16    // Return the coefficients of the desired row
17    return rowCoefficients;
18}
19
Not Sure What to Study? Take the 2-min Quiz

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

The time complexity of the given code is O(n^2) where n is the rowIndex. This quadratic time complexity arises because there are two nested loops: the outer loop runs from 2 to rowIndex (exclusive), and for each iteration of the outer loop, the inner loop runs backwards from i - 1 to 1, where i is the current iteration of the outer loop. Since i increases linearly, the total amount of work done is the sum of the first n integers, which leads to an O(n^2) time complexity.

The space complexity of the code is O(n) where n is the rowIndex. This space complexity is due to the list f which contains rowIndex + 1 elements. The space taken by the list is directly proportional to the rowIndex, hence the space complexity is linear.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«