118. Pascal's Triangle

📝 Problem Details

• Title: 118. Pascal's Triangle
• Link: https://leetcode.com/problems/pascals-triangle/
• Difficulty: Easy
• Tags/Categories: Dynamic-Programming Math

💡 Explanation of Solution

Pascal's Triangle is structured such that:
- the first and last element of each row is always 1
- each element in between, is the sum of the two elements directly above it 

- use a 2d vector to store results 

⌛ Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> triangle(numRows); // Initialize outer vector
 
        for (int i = 0; i < numRows; i++) {
            triangle[i].resize(i + 1, 1); // Resize row to (i+1) elements, all initialized to 1
 
            for (int j = 1; j < i; j++) { // Fill in the middle elements
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
        }
        return triangle;
    }
};