No result illustrationNo result illustration

DevLoom

search

Lets Connect

chevron right
Menu
Home

Home

Community

Community

Blog Posts

Blog Posts

Programming

Programming

Tech Topics

Tech Topics

Explore

Explore

Find Jobs

Find Jobs

Tags

Tags

DevLoomPerfect Place for devs
    profile

    Jubair

    upvoteupvote

    1

    downvote

    0

    star

    Pascal's Triangle Leetcode

    clock icon

    Asked 9 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.

    Google
    Math
    array
    easy

    Share

    Write your comment here !

    0 Responses