Pascals Triangle Ii - Leetcode Solution

Problem statement:

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it as shown below: 1 11 121 1331 14641

Example: Input: rowIndex = 3 Output: [1,3,3,1]

Solution:

The approach to solve this problem is to use the formula for a particular row in Pascal's triangle. We can use the formula to calculate the elements of the given row and return the row as an array.

The formula to calculate the ith element in the jth row of Pascal's triangle is given by:

P(j, i) = P(j-1, i-1) + P(j-1, i)

where P(j, i) represents the ith element in the jth row of the Pascal's triangle.

To solve the problem, we need to first initialize an array with the first row of Pascal's triangle, which is [1]. Then, we need to iterate from 0 to rowIndex-1 to calculate the subsequent rows of the Pascal's triangle. For each iteration, we need to initialize a new row and calculate its elements using the above formula. Finally, we return the rowIndexth row of the Pascal's triangle.

Code:

public List<Integer> getRow(int rowIndex) { List<Integer> row = new ArrayList<>(); row.add(1); for(int i=0; i<rowIndex; i++){ List<Integer> newRow = new ArrayList<>(); newRow.add(1); for(int j=1; j<row.size(); j++){ newRow.add(row.get(j-1) + row.get(j)); } newRow.add(1); row = newRow; } return row; }

Explanation:

We initialize the first row of the Pascal's triangle with [1] and add it to the row list. Then, we iterate from 0 to rowIndex-1 and calculate the subsequent rows of the Pascal's triangle.

For each iteration, we initialize a new row with [1] at the beginning and [1] at the end, and iterate over the elements of the previous row to calculate the current row using the formula mentioned above.

Finally, we return the rowIndexth row of the Pascal's triangle.

The time complexity of this approach is O(rowIndex^2) as we need to calculate the elements of each row. The space complexity is O(rowIndex) as we are storing only one row at a time.

1