118. Pascal's Triangle

Description

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: 5

Output:

[

[1],

[1, 1],

[1, 2, 1],

[1, 3, 3, 1],

[1, 4, 6, 4, 1]

]

Solutions

Solution 1

/**
 * Time complexity : O(N*N)
 * Space complexity : O(N*N)
 */

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

Solution 2

/**
 * Time complexity : O(N*N)
 * Space complexity : O(N*N)
 */

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> pascals = new ArrayList();
        if(numRows == 0) return pascals;
        
        List<Integer> row = null, prevRow = null;
        
        for(int i = 0; i < numRows; i++) {
            row = new ArrayList();
            for(int j = 0; j <= i; j++) {
                if(j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(prevRow.get(j-1)+prevRow.get(j));
                }
            }
            prevRow = row;
            pascals.add(row);
        }
        return pascals;
    }
}

Follow up