Problem Explanation

Pascal's triangle is a triangle where each number is the sum of the two directly above it. It begins with "1" at the top. In this problem, we're asked to return the kth index row of the Pascal's triangle. Remember that the row index starts from 0.

For Example: If the input is 3, the output will be [1,3,3,1].

Approach

The problem asks us to find the exact row in the Pascal's triangle without generating the whole triangle which could take a lot of time and memory for big values of rowIndex.

The optimal approach to solve this problem is using dynamic programming. Initially, we initialise the array, ans, with 1's. Then, from the third index of the rowIndex, for each i from 1 to i-1, we update ans[i] as the sum of ans[i] and ans[i-1]. The iteration process follows a reverse order in each row to avoid overwriting the values that are needed to get the next element in the row.

Python Solution

1
2python
3class Solution:
4    def getRow(self, rowIndex: int):
5        # Initalize the array with 1's
6        ans = [1] * (rowIndex + 1)
7        # Starting from third index
8        for i in range(2, rowIndex + 1):
9            # For each i from 1 to i-1
10            for j in range(1, i):
11                # Update ans[i] by sum of ans[i] and ans[i-1]
12                ans[i - j] += ans[i - j - 1]
13        return ans

Java Solution

1
2java
3class Solution {
4    public List<Integer> getRow(int rowIndex) {
5        List<Integer> ans = new ArrayList<>(rowIndex + 1);
6        // Initialize the array with 1's
7        for (int i = 0; i < rowIndex + 1; i++) {
8            ans.add(1);
9        }
10        // Starting from third index
11        for (int i = 2; i < rowIndex + 1; ++i)
12            // For each i from 1 to i-1
13            for (int j = i - 1; j > 0; --j)
14                // Update ans[j] by the sum of ans[j] and ans[j-1]
15                ans.set(j, ans.get(j) + ans.get(j - 1));
16        return ans;
17    }
18}

JavaScript Solution

1
2javascript
3class Solution {
4    getRow(rowIndex) {
5        // Initialize the array with 1's
6        let ans = new Array(rowIndex + 1).fill(1);
7        // Starting from third index
8        for (let i = 2; i <= rowIndex; ++i)
9            // For each i from 1 to i-1
10            for (let j = i - 1; j > 0; --j)
11                // Update ans[j] by the sum of ans[j] and ans[j-1]
12                ans[j] += ans[j - 1];
13        return ans;
14    }
15}

C++ Solution

1
2c++
3class Solution {
4 public:
5  vector<int> getRow(int rowIndex) {
6    // Initialize the array with 1's
7    vector<int> ans(rowIndex + 1, 1);
8    // Starting from third index
9    for (int i = 2; i <= rowIndex; ++i)
10      // For each i from 1 to i-1
11      for (int j = i - 1; j > 0; --j)
12        // Update ans[j] by the sum of ans[j] and ans[j-1]
13        ans[j] += ans[j - 1];
14    return ans;
15  }
16};

C# Solution

1
2csharp
3public class Solution {
4    public IList<int> GetRow(int rowIndex) {
5        IList<int> ans = new List<int>(new int[rowIndex + 1]);
6        // Initialize the array with 1's
7        for (int i = 0; i <= rowIndex; i++)
8            ans[i] = 1;
9        // Starting from third index
10        for (int i = 2; i <= rowIndex; ++i)
11            // For each i from 1 to i-1
12            for (int j = i - 1; j > 0; --j)
13                // Update ans[j] by the sum of ans[j] and ans[j-1]
14                ans[j] += ans[j - 1];
15        return ans;
16    }
17}

In all the solutions above, we initialise a vector or list with the size of rowIndex + 1 and fill it with 1s. This is the first row in Pascal's triangle. Then we start from the 3rd row (i = 2), we calculate each new element by summing the 2 elements directly above it which correspond to the jth and j - 1th indexes of the previous row.

Note: In a 0-indexed array, the rowIndex + 1 rows of Pascal's triangle correspond to rowIndex + 1 elements in the ans array.# Ruby Solution

1
2ruby
3class Solution
4    def get_row(row_index)
5        # Initialize the array with 1's
6        ans = Array.new(row_index + 1, 1)
7        # Starting from third index
8        (2..row_index).each do |i|
9            # For each i from 1 to i-1
10            (i - 1).downto(1) do |j|
11                # Update ans[j] by the sum of ans[j] and ans[j-1]
12                ans[j] += ans[j - 1]
13            end
14        end
15        ans
16    end
17end

R Solution

1
2R
3getRow <- function(rowIndex) {
4    # Initialize the array with 1's
5    ans <- rep(1, rowIndex + 1)
6    # Starting from third index
7    for(i in 3:(rowIndex + 1)){
8        # For each i from 1 to i-1
9        for(j in (i-1):2){
10            # Update ans[j] by the sum of ans[j] and ans[j-1]
11            ans[j] <- ans[j] + ans[j - 1]
12        }
13    }
14    ans
15}

Conclusion

As we can see, all of the solutions follow a similar approach - we initialise an array or list with 1s and then use two loops to update each position of the array based on the sum of its previous element and itself. The key points to take away would be the understanding of Pascal's Triangle and how its construction rules can be translated into an efficient iterative code process.

In terms of time complexity, all the given solutions above run in O(n^2) time where n is the number of rows we need to generate. This is because we have to iterate over each row and generate all of its elements. The space complexity for all the given solutions is O(n), as a single list of size rowIndex + 1 is used to generate all the elements of the current row while only using the previously computed values. This makes it a relatively efficient solution considering the constraints of the problem.