Pascal's Triangle - LeetCode

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.
Example:
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
Java Solution :
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(numRows == 0)
           return result;
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        result.add(row);
        for(int i=1;i<numRows;i++){
            List<Integer> prevRow = new ArrayList<Integer>();
            prevRow = result.get(i-1);
            row = new ArrayList<>();
            row.add(1);
            for(int j=1 ; j < i ; j++){
                row.add(prevRow.get(j-1)+prevRow.get(j));
            }
            row.add(1);
          result.add(row);
        }
        return result;
    }
}
Time Complexity : O(n*n)
Space Complexity : O(n*n)

No comments:

Post a Comment

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...