Scale Engineer

Pascal's Triangle

Easy
#0118Time: O(2^numRows)Space: O(numRows^2)15 companies
Patterns
Dynamic Programming
Data structures
Array
Companies
AccentureCiscoDeloitteGoldman Sachs

Prompt

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:

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= numRows <= 30

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the mathematical definition of Pascal's Triangle into a recursive function. Each element T(i, j) is calculated by the recursive formula T(i, j) = T(i-1, j-1) + T(i-1, j). The base cases are the edges of the triangle, where T(i, 0) = 1 and T(i, i) = 1.

Algorithm

  • Create a main list triangle to store the result.
  • Loop for i from 0 to numRows - 1:
    • Create a new list currentRow.
    • Loop for j from 0 to i:
      • Calculate the value at (i, j) using a recursive helper function computeValue(i, j).
      • Add the value to currentRow.
    • Add currentRow to triangle.
  • Return triangle.

Helper function computeValue(row, col):

  • If col == 0 or col == row, return 1.
  • Return computeValue(row - 1, col - 1) + computeValue(row - 1, col).

Walkthrough

We define a helper function, say getValue(row, col), that computes the value at a specific position in the triangle. The main function iterates from row = 0 to numRows - 1. For each row, it iterates from col = 0 to row. In the inner loop, it calls getValue(row, col) to compute the element and adds it to the current row's list.

The getValue(row, col) function works as follows: if col is 0 or col is equal to row, it returns 1 (base case). Otherwise, it makes two recursive calls: getValue(row - 1, col - 1) and getValue(row - 1, col), and returns their sum.

This method is straightforward but highly inefficient because it re-computes the same values multiple times. For instance, calculating T(5, 2) requires T(4, 1) and T(4, 2), and both of these require T(3, 1), leading to redundant calculations.

class Solution {    public List<List<Integer>> generate(int numRows) {        List<List<Integer>> triangle = new ArrayList<>();        for (int i = 0; i < numRows; i++) {            List<Integer> row = new ArrayList<>();            for (int j = 0; j <= i; j++) {                row.add(computeValue(i, j));            }            triangle.add(row);        }        return triangle;    }     private int computeValue(int row, int col) {        if (col == 0 || col == row) {            return 1;        }        return computeValue(row - 1, col - 1) + computeValue(row - 1, col);    }}

Complexity

Time

O(2^numRows)

Space

O(numRows^2)

Trade-offs

Pros

  • Simple to understand as it directly follows the mathematical definition.

Cons

  • Extremely inefficient due to massive redundant computations.

  • Will likely result in a 'Time Limit Exceeded' error for larger inputs.

Solutions

class Solution { public List < List < Integer >> generate ( int numRows ) { List < List < Integer >> f = new ArrayList <>(); f . add ( List . of ( 1 )); for ( int i = 0 ; i < numRows - 1 ; ++ i ) { List < Integer > g = new ArrayList <>(); g . add ( 1 ); for ( int j = 0 ; j < f . get ( i ). size () - 1 ; ++ j ) { g . add ( f . get ( i ). get ( j ) + f . get ( i ). get ( j + 1 )); } g . add ( 1 ); f . add ( g ); } return f ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem