119. Pascal's Triangle II

Description

Given an integer rowIndex, return the rowIndex-th (0-indexed) row of Pascal's Triangle.

In Pascal's Triangle, each number is the sum of the two numbers directly above it.

Intuition

Pascal's Triangle is a well-known mathematical construct where each row represents the coefficients of the binomial expansion. The rowIndex-th row can be generated iteratively by leveraging the relationship between the elements of consecutive rows.

Approach

1. Initialization: - Start with an array result of size rowIndex + 1, initialized with zeros. Set the first element to 1 because the first element of each row in Pascal's Triangle is always 1.
2. Iterative Construction: - For each row from 1 to rowIndex, update the result array in reverse order to avoid overwriting values that are yet to be used. - Specifically, for each index i in the row, update result[i] as result[i] + result[i-1].
3. Final Output: - After constructing the row iteratively, the result array contains the values of the rowIndex-th row of Pascal's Triangle.

Complexity

Time Complexity:

(O(n^2)), where n is the rowIndex. This is due to the nested loop where each element in a row is computed based on the previous row.

Space Complexity:

(O(n)), where n is the rowIndex. Only a single array of size rowIndex + 1 is used to store the row values.

Code

C++

class Solution {
public:
    vector getRow(int rowIndex) {
        vector result(rowIndex + 1, 0);
        result[0] = 1;

        for (int row = 1; row <= rowIndex; ++row) {
            result[row] = 1;

            for (int index = row - 1; index > 0; --index) {
                result[index] += result[index - 1];
            }
        }

        return result;
    }
};

Python

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        result = [0] * (rowIndex + 1)
        result[0] = 1

        for row in range(1, rowIndex + 1):
            result[row] = 1

            for index in range(row - 1, 0, -1):
                result[index] += result[index - 1]

        return result

Java

class Solution {
    public List getRow(int rowIndex) {
        List result = new ArrayList<>(Collections.nCopies(rowIndex + 1, 0));
        result.set(0, 1);

        for (int row = 1; row <= rowIndex; ++row) {
            result.set(row, 1);

            for (int index = row - 1; index > 0; --index) {
                result.set(index, result.get(index) + result.get(index - 1));
            }
        }

        return result;
    }
}

JavaScript

function getRow(rowIndex) {
    const result = new Int32Array(rowIndex + 1);

    result[0] = 1;

    for (let row = 1; row <= rowIndex; ++row) {
        result[row] = 1;

        for (let index = row - 1; index > 0; --index) {
            result[index] += result[index - 1];
        }
    }

    return result;
}