Leetcode 119. Pascal's Triangle II
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 1
s. 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 j
th and j - 1
th 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 1
s 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.
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.