Pascal's Triangle Leetcode

clock icon

Asked 3 months ago

message

0Comments

eye

0 Views

Pascal's Triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. Here's how we can approach this problem:

  1. We'll create a 2D vector to store the triangle.
  2. The first row always contains just one element: 1.
  3. For each subsequent row:
    • The first and last elements are always 1.
    • The middle elements are the sum of the two numbers directly above it in the previous row.

Let's implement this solution:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> triangle;
        
        // Handle edge case
        if (numRows == 0) return triangle;
        
        // First row is always [1]
        triangle.push_back({1});
        
        for (int i = 1; i < numRows; i++) {
            vector<int> row;
            vector<int>& prevRow = triangle[i-1];
            
            // First element of the row is always 1
            row.push_back(1);
            
            // Calculate middle elements
            for (int j = 1; j < i; j++) {
                row.push_back(prevRow[j-1] + prevRow[j]);
            }
            
            // Last element of the row is always 1
            row.push_back(1);
            
            triangle.push_back(row);
        }
        
        return triangle;
    }
};

Now, let me explain the code and the approach:

  1. We start by creating a 2D vector called triangle to store our result.
  2. We handle the edge case where numRows is 0 by returning an empty triangle.
  3. We always add the first row, which is just [1].
  4. Then, we iterate from the second row (index 1) up to the numRows-th row:
    • We create a new vector row for each row.
    • We add 1 as the first element of each row.
    • For the middle elements, we sum the two numbers from the previous row.
    • We add 1 as the last element of each row.
    • Finally, we add the completed row to our triangle.
  5. After generating all rows, we return the triangle.

This solution has a time complexity of O(numRows^2) because we're iterating through each element of the triangle. The space complexity is also O(numRows^2) to store the entire triangle.

Share

Write your comment here !

0 Responses