Question

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

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:

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

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

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;
};

impl Solution {
    #[allow(dead_code)]
    pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
        let mut ret_vec: Vec<Vec<i32>> = Vec::new();
        let mut cur_vec: Vec<i32> = Vec::new();

        for i in 0..num_rows as usize {
            let mut new_vec: Vec<i32> = vec![1; i + 1];
            for j in 1..i {
                new_vec[j] = cur_vec[j - 1] + cur_vec[j];
            }
            cur_vec = new_vec.clone();
            ret_vec.push(new_vec);
        }

        ret_vec
    }
}

118 - Pascal's Triangle

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions