Question

Formatted question description: https://leetcode.ca/all/118.html

118. Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

@tag-array

Algorithm

The first and last number of each line is 1. Starting from the third line, each number in the middle is the sum of the left and right numbers of the previous line.

Code

Java

public class Pascals_Triangle {

	public class Solution {
	    public List<List<Integer>> generate(int numRows) {
	        
	    	List<List<Integer>> list = new ArrayList<>();
	    	
	    	if (numRows <= 0) {
	    		return list;
	    	}

	    	List<Integer> prev = new ArrayList<>();
	    	prev.add(1);
	    	list.add(prev);
	    	if (numRows == 1) {
	    		return list;
	    	}
	    	
	    	for (int i = 2; i <= numRows; i++) {
	    		List<Integer> current = new ArrayList<>(prev); // @note: don't need to deepcopy prev list

    			for (int j = 1; j < i; j++) { // not start from 0, since index=0 is always 1
	    			
	    			if (j < prev.size()) {
	    				int add = prev.get(j) + prev.get(j - 1); // j starts at 1, so j-1 guaranteed ok
	    				current.set(j, add);
	    			} else {
	    				// current.set(j, 1);
	    				current.add(1); // @note: the last one, just add, not set
	    			}
	    		}
	    		
	    		list.add(current);
	    		prev = current;
	    	}
	    	
	    	return list;
	    }
	}

}

All Problems

All Solutions