Arrays - Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown in below diagram:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Input: numRows = 1
Output: [[1]]

Solution using previous row values

In this approach, we are simply going to use previous row values and compute the values for current row.

We will create a function usingPreviousRowValues that takes input argument numRows.
We are then going to create create a variable result of type List<List<Integer>>, that is our return type. List<List<Integer>> result = new ArrayList<>();
In the first step, we are going to create the first row elements, that is [1] and add it to the result list. If the numRows is 1, then we simply return result at this step.
Next, we will also add second row elements, that is [1, 1] and add it to the result.
Then, loop through from 3^rd row (i.e. 2^nd index) until numRows, add element '1' on both ends of the row, then from index 1 until currentRow add previous row's elements at index i-1 and i as shown below. currentRow.add(previousRow.get(j-1) + previousRow.get(j));

import java.util.ArrayList; import java.util.List; public class PascalsTriangle { static List<List<Integer>> usingPreviousRowValues (int numRows) { List<List<Integer>> result = new ArrayList<>(); result.add(List.of(1)); if(numRows == 1) { return result; } // then add second row as well result.add(List.of(1, 1)); for(int i=2; i<numRows; i++) { List<Integer> previousRow = result.get(i-1); List<Integer> currentRow = new ArrayList<>(); currentRow.add(1); for(int j=1; j<i; j++) { currentRow.add(previousRow.get(j-1) + previousRow.get(j)); } currentRow.add(1); result.add(currentRow); } return result; } }

Complexity Analysis:

Time complexity: Above code runs in O(n²) time where n is the input numRows. This is because, we are looping numRows times, and for each numRow we are again looping through previous row values.
Space complexity: O(n²) for the result.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis: