Welcome to Subscribe On Youtube

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
• C++
• Python
• Go
• TypeScript
• Javascript

• 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;
  	    }
  	}
  
  }
  
  
  ############
  
  class Solution {
      public List<List<Integer>> generate(int numRows) {
          List<List<Integer>> ans = new ArrayList<>();
          for (int i = 0; i < numRows; ++i) {
              List<Integer> t = new ArrayList<>();
              for (int j = 0; j < i + 1; ++j) {
                  int v = j == 0 || j == i ? 1 : ans.get(i - 1).get(j) + ans.get(i - 1).get(j - 1);
                  t.add(v);
              }
              ans.add(t);
          }
          return ans;
      }
  }
  

• // OJ: https://leetcode.com/problems/pascals-triangle/
  // Time: O(N^2)
  // Space: O(1)
  class Solution {
  public:
      vector<vector<int>> generate(int numRows) {
          vector<vector<int>> ans(numRows);
          for (int i = 0; i < numRows; ++i) {
              ans[i] = vector<int>(i + 1, 1);
              for (int j = 1; j < i; ++j) ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
          }
          return ans;
      }
  };
  

• class Solution:
      def generate(self, numRows: int) -> List[List[int]]:
          ans = []
          for i in range(numRows):
              t = [
                  1 if j == 0 or j == i else ans[-1][j] + ans[-1][j - 1]
                  for j in range(i + 1)
              ]
              ans.append(t)
          return ans
  
  ############
  
  class Solution(object):
    def generate(self, numRows):
      """
      :type numRows: int
      :rtype: List[List[int]]
      """
      ans = [[1] * n for n in range(1, numRows + 1)]
      for i in range(1, numRows + 1):
        for j in range(0, i - 2):
          ans[i - 1][1 + j] = ans[i - 2][j] + ans[i - 2][j + 1]
      return ans
  
  

• func generate(numRows int) [][]int {
  	ans := make([][]int, numRows)
  	for i := range ans {
  		t := make([]int, i+1)
  		t[0], t[i] = 1, 1
  		for j := 1; j < i; j++ {
  			t[j] = ans[i-1][j] + ans[i-1][j-1]
  		}
  		ans[i] = t
  	}
  	return ans
  }
  

• function generate(numRows: number): number[][] {
      if (numRows == 0) return [];
      let ans = [[1]];
      for (let i = 1; i < numRows; ++i) {
          ans.push(new Array(i + 1).fill(1));
          let half = i >> 1;
          for (let j = 1; j <= half; ++j) {
              let cur = ans[i - 1][j - 1] + ans[i - 1][j];
              ans[i][j] = cur;
              ans[i][i - j] = cur;
          }
      }
      return ans;
  }
  
  

• const generate = function (numRows) {
      let arr = [];
      for (let i = 0; i < numRows; i++) {
          let row = [];
          row[0] = 1;
          row[i] = 1;
          for (let j = 1; j < row.length - 1; j++) {
              row[j] = arr[i - 1][j - 1] + arr[i - 1][j];
          }
          arr.push(row);
      }
      return arr;
  };
  
  /**
   *  Author: Mcnwork2018
   */
  
  var generate = function (numRows) {
      if (numRows === 0) return [];
      if (numRows === 1) return [[1]];
      if (numRows === 2) return [[1], [1, 1]];
      let triangleArray = [[1], [1, 1]];
      for (let i = 2; i < numRows; ++i) {
          triangleArray[i] = [];
          for (let j = 0; j < i + 1; ++j) {
              if (j === 0 || j === i) {
                  triangleArray[i][j] = 1;
              } else {
                  triangleArray[i][j] =
                      triangleArray[i - 1][j - 1] + triangleArray[i - 1][j];
              }
          }
      }
      return triangleArray;
  };
  
  

All Problems

All Solutions