[LeetCode] 118. Pascal’s Triangle

Problem

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

Solution

Logic

1. 리스트를 생성한다.

2. 생성한 리스트의 첫 요소 혹은 마지막 요소는 1로 지정하고 값을 채우지 못한 요소가 있다면 직전 리스트의 직전 인덱스와 현재 인덱스에 해당하는 요소를 더한 값으로 지정한다.

3. 요소가 채워진 리스트를 반환을 위한 리스트에 담는다.

4. 위 과정을 길이가 1인 리스트부터 정수 numsRows인 리스트까지 진행한다.

   Code

   class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < i + 1; j++) {
                if (j == 0 || j == i) row.add(1);
                else row.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
            } list.add(row);
        } return list;
    }
   }
   

   Time Complexity

   • 아래 이중 반복문은 1 + 2 + … + n = (n * (n + 1)) / 2의 반복 계산을 통해 O(n^2)의 시간 복잡도를 가진다. 따라서 본 솔루션은 O(n^2)의 시간 복잡도를 가진다.

     List<List<Integer>> list = new ArrayList<>();
     for (int i = 0; i < numRows; i++) {
      List<Integer> row = new ArrayList<>();
      for (int j = 0; j < i + 1; j++) {
        if (j == 0 || j == i) row.add(1);
        else row.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
      } list.add(row);
     }