Gowthaman Ravi
Gowthy's Blog

Gowthy's Blog

Dynamic Programming | Pascal's Triangle

Gowthaman Ravi's photo
Gowthaman Ravi
·Jan 26, 2022·

Subscribe to my newsletter and never miss my upcoming articles

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: LEETCODE GIF.gif

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

Java Solution

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

C++ Solution

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector< int> L1;
        vector<vector<int>> res;
        if(numRows==0)
            return res;

        L1.push_back(1);
        res.push_back(L1);
        if(numRows==1)
            return res;

        vector< int>L2 ={1,1};
        res.push_back(L2);
        if(numRows==2)
            return res;

        for( int i=3;i<=numRows;i++){
            L1.clear();
            L1.push_back(1);
            for(int j=1;j<L2.size();j++){
                L1.push_back(L2[j-1]+L2[j]);
            }
            L1.push_back(1);
            res.push_back(L1);
            L2=L1;
        }
        return res;
    }
};
 
Share this