Question

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

119 - Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

@tag-array

Algorithm

Except for the first and last numbers, the other numbers are the sum of the left and right values in the previous line. Then we only need two for loops.

Except for the first number being 1, the following numbers are the sum of the value of the previous loop plus the value of the previous position, and keep updating the value of each position. You can get the number in the nth row.

Code

Java

  • public class Pascals_Triangle_II {
    
        public class Solution_noExtraSpace {
            public List<Integer> getRow(int rowIndex) {
    
                List<Integer> res = new ArrayList<>();
                res.add(1);
                for (int i = 1; i <= rowIndex; ++i) {
                    for (int j = i; j >= 1; --j) {
                        res.set(j, res.get(j) + res.get(j - 1));
                    }
                }
                return res;
    
            }
        }
    
        public class Solution {
            public List<Integer> getRow(int rowIndex) {
    
                List<Integer> row = new ArrayList<>();
    
                if (rowIndex < 0) {
                    return row;
                }
    
                row.add(1);
                if (rowIndex == 0) {
                    return row;
                }
    
                for (int i = 2; i <= rowIndex + 1; i++) {
                    List<Integer> current = new ArrayList<>(row);
    
                    for (int j = 1; j < i; j++) {
    
                        if (j < row.size()) {
                            int add = row.get(j) + row.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
                        }
                    }
    
                    row = current;
                }
    
                return row;
    
            }
        }
    }
    
    
    
  • // OJ: https://leetcode.com/problems/pascals-triangle-ii/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> ans(rowIndex + 1, 1);
            for (int i = 2; i <= rowIndex; ++i) {
                for (int j = i - 1; j > 0; --j) ans[j] += ans[j - 1];
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        fact = [1] * (rowIndex + 1)
        ans = [1] * (rowIndex + 1)
        for i in range(1, rowIndex + 1):
          fact[i] = fact[i - 1] * i
        for i in range(1, rowIndex):
          ans[i] = fact[-1] / (fact[i] * fact[rowIndex - i])
        return ans
    
    

All Problems

All Solutions