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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class PascalTriangle {
5 public static List<Integer> getRow(int rowIndex) {
6 List<Integer> row = new ArrayList<>();
7 for (int i = 0; i <= rowIndex; i++) {
8 row.add(0);
9 }
10 row.set(0, 1);
11 for (int i = 1; i <= rowIndex; i++) {
12 for (int j = i; j > 0; j--) {
13 row.set(j, row.get(j) + row.get(j - 1));
14 }
15 }
16 return row;
17 }
18
19 public static void main(String[] args) {
20 List<Integer> result = getRow(3);
21 System.out.println(result);
22 }
23}This Java program uses an ArrayList for dynamic sizing and iteratively computes each element of the desired row, updating 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.
1#include <vector>
class Solution {
public:
std::vector<int> getRow(int rowIndex) {
std::vector<int> row(rowIndex + 1, 1);
long long C = 1;
for (int i = 1; i < rowIndex; ++i) {
C = C * (rowIndex - i + 1) / i;
row[i] = C;
}
return row;
}
};
int main() {
Solution sol;
std::vector<int> result = sol.getRow(3);
for (int num : result) {
std::cout << num << " ";
}
return 0;
}This C++ solution calculates each element of the row using the binomial coefficient, effectively leveraging integer math skills to minimize algebraic errors and inaccuracies.