Given an integer numRows where 1 <= numRows <= 30. Pascal's Triangle begins with one 1, and each interior value is the sum of the two values directly above it. Return the first numRows rows of Pascal's Triangle.
Example 1
Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explanation: The first row is [1]. Every next row starts and ends with 1, and each interior value is formed by adding two adjacent values from the previous row.
Example 2
Input: numRows = 1
Output: [[1]]
Explanation: Only the first row is requested, so the triangle contains a single row with one value.
Brute Force Approach
Each requested cell can be evaluated directly from Pascal's Triangle definition. Boundary cells are 1. An interior cell asks for the two cells above it, and those cells ask for their own parents.
Algorithm
Create an empty answer that will store all requested rows.
Generate row positions from
0tonumRows - 1; the minimum valid inputnumRows = 1creates only row0.For every column in the current row, compute that cell through the recursive triangle definition.
Return
1directly for boundary cells where the column is the first or last position.For an interior cell, add the upper-left and upper-right recursive values from the previous row.
Recursion terminates because every recursive request moves to a smaller row, and generation stops after
numRowsrows.
Dry Run
PT recursion
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Returns one value from Pascal's Triangle. int valueAt(int row, int col) { // Boundary values are always 1. if (col == 0 || col == row) { return 1; } // Add the two values directly above the current cell. return valueAt(row - 1, col - 1) + valueAt(row - 1, col); }public: // Returns the first numRows rows of Pascal's Triangle. vector<vector<int>> generate(int numRows) { vector<vector<int>> triangle; // Build every requested row from top to bottom. for (int row = 0; row < numRows; row++) { vector<int> current; // Compute every cell in this row independently. for (int col = 0; col <= row; col++) { current.push_back(valueAt(row, col)); } triangle.push_back(current); } return triangle; }};// Prints a triangle in list form.void printTriangle(const vector<vector<int>>& triangle) { cout << "["; int rowCount = triangle.size(); // Print each row in order. for (int row = 0; row < rowCount; row++) { cout << "["; int colCount = triangle[row].size(); // Print every value in the current row. for (int col = 0; col < colCount; col++) { cout << triangle[row][col]; // Add a separator between values in the same row. if (col + 1 < colCount) { cout << ", "; } } cout << "]"; // Add a separator between completed rows. if (row + 1 < rowCount) { cout << ", "; } } cout << "]\n";}// Driver codeint main() { int numRows = 6; // instance for class Solution Solution sol; vector<vector<int>> answer = sol.generate(numRows); printTriangle(answer); return 0;}Complexity Analysis
Time Complexity: O(2ⁿ), where n is numRows, because recursive cell evaluation recomputes many smaller cells while generating the triangle.
Space Complexity: O(n) auxiliary space is used by the recursion depth, and the returned triangle itself stores O(n²) values.
Optimal Approach
Instead of recomputing cells from scratch, each completed row can be reused to build the next row. This matches the structure of Pascal's Triangle naturally.
Each new row starts filled with 1. Only the interior positions need calculation. An interior position is the sum of the value above-left and the value above-right from the previous row. Since every returned value is written once, the running time is as small as the output size allows.
Algorithm
Create an empty triangle to store the rows that must be returned.
Build rows from
0tonumRows - 1; fornumRows = 1, the first row is created and returned.Initialize each current row with
1in every position so the boundary values are already correct.For each interior position, add the two adjacent values from the previous row and place the sum in the current row.
Append the completed current row to the triangle before moving to the next row.
Stop after
numRowsrows have been appended and return the triangle.
Dry Run
Iterative
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the first numRows rows of Pascal's Triangle. vector<vector<int>> generate(int numRows) { vector<vector<int>> triangle; // Build each row from top to bottom. for (int row = 0; row < numRows; row++) { vector<int> current(row + 1, 1); // Fill only the interior positions from the previous row. for (int col = 1; col < row; col++) { current[col] = triangle[row - 1][col - 1] + triangle[row - 1][col]; } triangle.push_back(current); } return triangle; }};// Prints a triangle in list form.void printTriangle(const vector<vector<int>>& triangle) { cout << "["; int rowCount = triangle.size(); // Print each row in order. for (int row = 0; row < rowCount; row++) { cout << "["; int colCount = triangle[row].size(); // Print every value in the current row. for (int col = 0; col < colCount; col++) { cout << triangle[row][col]; // Add a separator between values in the same row. if (col + 1 < colCount) { cout << ", "; } } cout << "]"; // Add a separator between completed rows. if (row + 1 < rowCount) { cout << ", "; } } cout << "]\n";}// Driver codeint main() { int numRows = 6; // instance for class Solution Solution sol; vector<vector<int>> answer = sol.generate(numRows); printTriangle(answer); return 0;}Complexity Analysis
Time Complexity: O(n²) , where n is numRows, because every value in the returned triangle is created once.
Space Complexity: O(1) auxiliary space is used beyond the returned triangle, and the returned triangle stores O(numRows²) values.
Interview follow-up Questions
The output itself contains O(numRows²) values. Any complete solution must write all of them, so the row-building approach matches the unavoidable output size.
Be the first to add a comment.