2023-10-16 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge
|

Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 16

Description

Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

 

Constraints:

  • 0 <= rowIndex <= 33

 

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Solution

constexpr int combination(int m, int n) {
  m = n - m > m ? m : n - m;
  long long result = 1;
  for(int i = 0; i < m; ++i) {
    result *= n - i;
    result /= i + 1;
  }
  return result;
}
class Solution {
public:
  vector<int> getRow(int rowIndex) {
    vector<int> answer(rowIndex + 1);
    for(int i = 0; i <= rowIndex; ++i) {
      answer[i] = combination(i, rowIndex);
    }
    return answer;
  }
};

// Accepted
// 34/34 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 52.72 % of cpp submissions (6.4 MB)
Algorithm