Sponsored
Sponsored
The iterative approach builds each row of Pascal's Triangle from the topmost row down to the target row, updating values in-place. The key observation is that each element at position j in a row is the sum of the element at position j and j-1 from the previous row. By starting from the end of the row, you can use the same array for updating values without overwriting the necessary data.
Time Complexity: O(n^2) where n is rowIndex as it involves nested iteration to build each row.
Space Complexity: O(n) for storing the result row.
1#include <iostream>
2#include <vector>
3
4std::vector<int> getRow(int rowIndex) {
5 std::vector<int> row(rowIndex + 1, 0);
6 row[0] = 1;
7 for (int i = 1; i <= rowIndex; ++i) {
8 for (int j = i; j > 0; --j) {
9 row[j] += row[j - 1];
10 }
11 }
12 return row;
13}
14
15int main() {
16 int rowIndex = 3;
17 std::vector<int> result = getRow(rowIndex);
18 for (int num : result) {
19 std::cout << num << " ";
20 }
21 return 0;
22}This C++ solution makes use of a vector to initialize the required row with zeroes except the first element. Updates are made iteratively in place.
This approach utilizes the combinatorial formula for a specific row in Pascal's Triangle. Specifically, the k-th element in the n-th row is given by the binomial coefficient: C(n, k) = n! / (k! * (n-k)!). Using this fact, we can derive all the values of the row without constructing the triangle iteratively.
Time Complexity: O(n).
Space Complexity: O(n) for storing the row.
1using System.Collections.Generic;
public class Solution {
public IList<int> GetRow(int rowIndex) {
IList<int> row = new List<int> { 1 };
long C = 1;
for (int i = 1; i <= rowIndex; i++) {
C = C * (rowIndex - i + 1) / i;
row.Add((int)C);
}
return row;
}
public static void Main() {
Solution sol = new Solution();
var result = sol.GetRow(3);
Console.WriteLine(string.Join(", ", result));
}
}This C# program calculates the row of Pascal's Triangle using the binomial coefficient with iteratively computed products and divisions.