Given an integer rowIndex representing a 0-indexed row in Pascal's Triangle. Every boundary value is 1, and every interior value is the sum of the two numbers directly above it. Return the row at rowIndex.
Example 1
Input: rowIndex = 3
Output: [1, 3, 3, 1]
Explanation: Row 0 is [1], row 1 is [1, 1], row 2 is [1, 2, 1], and row 3 is [1, 3, 3, 1].
Example 2
Input: rowIndex = 5
Output: [1, 5, 10, 10, 5, 1]
Explanation: The fifth 0-indexed row has six values. Each interior value is formed by adding the two values above it from row 4.
Brute Force Approach
The direct method builds Pascal's Triangle from row 0 up to the requested row. Each row is kept, so every value needed by the next row is available from the row above.
This follows the triangle definition exactly. Boundary values are placed as 1, and interior values are formed from the two values directly above. It is easy to understand, but it stores rows that are not needed after the target row is produced.
Algorithm
Create an empty triangle that will store every row from the top to the requested row.
Build rows in increasing order, beginning with row
0; forrowIndex = 0, the first row itself is the answer.Fill each new row with boundary value
1at both ends.For every interior position, add the upper-left and upper-right values from the previous row.
After each row is completed, store it inside the triangle.
Stop once the requested row has been built and return that row.
Dry Run
Pascal Triangle-II
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the requested row of Pascal's Triangle. vector<int> getRow(int rowIndex) { vector<vector<int>> triangle; // Build every row from the top through the requested index. for (int row = 0; row <= rowIndex; row++) { vector<int> current(row + 1, 1); // Fill interior positions from the two values above. for (int col = 1; col < row; col++) { current[col] = triangle[row - 1][col - 1] + triangle[row - 1][col]; } triangle.push_back(current); } return triangle[rowIndex]; }};// Driver codeint main() { int rowIndex = 5; // instance for class Solution Solution sol; vector<int> answer = sol.getRow(rowIndex); for (int value : answer) { cout << value << " "; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(rowIndex²), because all rows up to the requested row are constructed and the total number of generated values is quadratic.
Space Complexity: O(rowIndex²), because the full triangle is stored before returning the requested row.
Space Optimisation
The full triangle is not necessary because a new row depends only on the row immediately above it. A single row container can be updated repeatedly until it becomes the requested row. Values are updated from right to left, so the previous-left value is still available when the current position is computed. This keeps the Pascal rule correct while using only linear storage.
Algorithm
Create one row container of length
rowIndex + 1and set the first value to1.Expand the row one level at a time; for
rowIndex = 0, the initial container is already complete.During each expansion, update positions from right to left so previous-row values are not overwritten too early.
Replace each active position by adding its current value and the value immediately to its left.
Continue until the requested row index has been reached.
Return the single row container as the answer.
Dry Run
Pascal Triangle-II
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the requested row of Pascal's Triangle. vector<int> getRow(int rowIndex) { vector<int> row(rowIndex + 1, 0); row[0] = 1; // Build each next row inside the same container. for (int level = 1; level <= rowIndex; level++) { // Update from right to left to preserve previous-row values. for (int col = level; col >= 1; col--) { row[col] = row[col] + row[col - 1]; } } return row; }};// Driver codeint main() { int rowIndex = 5; // instance for class Solution Solution sol; vector<int> answer = sol.getRow(rowIndex); for (int value : answer) { cout << value << " "; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(rowIndex²), because the row is expanded level by level and each level updates a growing number of positions.
Space Complexity: O(rowIndex), because only the returned row container is stored.
Optimal Approach
Each value in the 0-indexed row n is a binomial coefficient. The value at column c is C(n, c). Since the next coefficient can be derived from the previous one, the row can be generated directly from left to right.
The first value is always C(n, 0) = 1. For every next column, the relation C(n, c) = C(n, c - 1) * (n - c + 1) / c gives the next value exactly. This avoids constructing earlier rows and reduces the time to linear.
Algorithm
Start the result row with the first coefficient
1; forrowIndex = 0, this is already the complete answer.Generate each next column value from the previous coefficient using the binomial coefficient relation.
Multiply before dividing so the integer coefficient is computed exactly.
Use a wider intermediate numeric type in fixed-width languages to avoid temporary multiplication overflow.
Append every generated coefficient to the result row.
Stop after the coefficient for column
rowIndexhas been appended and return the row.
Dry Run
Pascal Triangle-II
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the requested row of Pascal's Triangle. vector<int> getRow(int rowIndex) { vector<int> result; long long current = 1; result.push_back(1); // Generate each next coefficient from the previous coefficient. for (int col = 1; col <= rowIndex; col++) { current = current * (rowIndex - col + 1) / col; // Final values fit in int under the given constraints. result.push_back(current); } return result; }};// Driver codeint main() { int rowIndex = 5; // instance for class Solution Solution sol; vector<int> answer = sol.getRow(rowIndex); for (int value : answer) { cout << value << " "; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(rowIndex), because exactly one coefficient is generated for each position in the requested row.
Space Complexity: O(rowIndex), because the returned row contains rowIndex + 1 values; auxiliary space besides the answer is O(1).
Interview follow-up Questions
The formula produces each required value directly from the previous value. It avoids building earlier rows, so the running time becomes linear in the number of returned values.
Be the first to add a comment.