Vansh Aggarwal

Posted on Apr 7

LeetCode Solution: 118. Pascal's Triangle

#leetcode #dsa #programming #tutorial

Diving into LeetCode 118: Pascal's Triangle – A Beginner's Guide to Dynamic Programming!

Hey fellow coders! 👋 Vansh2710 here, your friendly neighborhood competitive programmer, ready to demystify another classic LeetCode problem. Today, we're tackling Problem 118: Pascal's Triangle. Don't let the mathematical name scare you – this problem is a fantastic entry point into thinking about patterns and building solutions iteratively. Let's conquer it together!

Understanding the Puzzle: What is Pascal's Triangle?

Imagine building a pyramid of numbers. That's essentially what Pascal's Triangle is!

The problem asks us to generate the first numRows of this famous triangle.

Here's how it works:

Each row starts and ends with the number 1.
Every other number in a row is the sum of the two numbers directly above it in the previous row.

Let's look at the example: numRows = 5

      [1]          <- Row 0
     [1,1]         <- Row 1
    [1,2,1]        <- Row 2
   [1,3,3,1]       <- Row 3
  [1,4,6,4,1]      <- Row 4

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

The constraints are pretty small (1 <= numRows <= 30), hinting that a straightforward approach will work just fine!

The "Aha!" Moment: Uncovering the Pattern

The core intuition for Pascal's Triangle lies in its recursive definition. If you look closely at how each number (that isn't a 1) is formed, you'll see a clear pattern:

Row 0: [1] (Base case)
Row 1: [1, 1] (Base case)
Row 2: [1, (1+1), 1] -> [1, 2, 1]
- The 2 comes from summing the 1 and 1 from Row 1 directly above it.
Row 3: [1, (1+2), (2+1), 1] -> [1, 3, 3, 1]
- The first 3 comes from 1+2 (from Row 2).
- The second 3 comes from 2+1 (from Row 2).

This "sum of two numbers directly above" rule is our golden key! This means we can build the triangle row by row, using the previously generated row to calculate the current one. This is a classic pattern for dynamic programming or iterative construction.

Our Step-by-Step Approach

Let's break down how we'll construct the triangle programmatically:

Initialize Result: We need a way to store all the rows. A vector<vector<int>> (or List<List<Integer>> in Java) is perfect for this. Let's call it ans.
Handle First Row (Base Case):
- If numRows is 0, return an empty ans. (Though constraints say numRows >= 1)
- The first row is always [1]. Add this to ans.
Iterate and Build (Row by Row):
- Start a loop from the second row (i = 1) up to numRows - 1.
- For each row i we are currently building:
  - Create a new vector<int> (or List<Integer>) for the current row, let's call it temp.
  - The first element of every row is 1. So, temp.push_back(1).
  - Calculate inner elements: Now, loop from j = 1 up to i - 1.
    - Each element temp[j] will be the sum of ans[i-1][j-1] and ans[i-1][j].
    - ans[i-1] refers to the previous row.
    - j-1 and j are the indices in the previous row that sum up to the current element.
  - The last element of every row is 1. So, temp.push_back(1).
  - Finally, add the temp row to our ans result.
Return ans: After the loop completes, ans will contain all numRows of Pascal's Triangle.

Let's refine step 3 slightly, using a clever C++ vector constructor to pre-fill the 1s.
The vector<int> temp(i + 1, 1); line is super handy here. It creates a vector of size i+1 and initializes all elements to 1. This automatically handles the leading and trailing 1s for each row. We then just need to update the middle elements.

The Code

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans; // This will store our final Pascal's Triangle

        // Loop through each row we need to generate
        for (int i = 0; i < numRows; ++i) {
            // Create a new vector for the current row
            // Each row 'i' has 'i + 1' elements.
            // Initialize all elements to 1. This handles the leading and trailing 1s automatically.
            vector<int> temp(i + 1, 1);

            // Calculate the inner elements for rows starting from the second row (i=1)
            // The first and last elements are already 1, so we iterate from j=1 up to i-1
            if (i >= 2) { // Only calculate inner elements for rows with at least 3 elements (i.e., row index 2 or more)
                for (int j = 1; j < i; ++j) {
                    // The current element is the sum of the two elements directly above it
                    // from the previous row (ans[i-1]).
                    temp[j] = ans[i - 1][j - 1] + ans[i - 1][j];
                }
            }
            // Add the newly constructed row to our answer
            ans.push_back(temp);
        }
        return ans; // Return the complete triangle
    }
};

Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(numRows^2)
- We have an outer loop that runs numRows times (for each row).
- Inside this loop, we have an inner loop that calculates the elements for the current row. For row i, this inner loop runs i-1 times (effectively O(i)).
- Summing up the work: 1 + 2 + 3 + ... + (numRows - 1) which is approximately (numRows * (numRows - 1)) / 2. This simplifies to O(numRows^2).
Space Complexity: O(numRows^2)
- We are storing the entire Pascal's Triangle.
- The total number of elements in numRows rows is 1 + 2 + 3 + ... + numRows, which is (numRows * (numRows + 1)) / 2.
- This also simplifies to O(numRows^2).

Given the constraint numRows <= 30, 30^2 = 900 operations, which is incredibly fast! So, this solution is very efficient for the given constraints.

Key Takeaways

Pattern Recognition is Key: Many LeetCode problems (especially those involving sequences or grids) can be solved by identifying a repeating pattern or a relationship between current and previous states.
Iterative Construction (Dynamic Programming Light): When you can build a solution step-by-step, using results from previous steps, you're often employing a form of dynamic programming. You don't always need complex memoization tables; sometimes, just building iteratively works!
Base Cases are Crucial: Properly handling the first few rows (or initial conditions) is essential before generalizing the pattern.
Language Features Can Help: Using vector<int> temp(i + 1, 1); in C++ is a nice example of how knowing your language's features can lead to cleaner, more concise code.

This problem is a fantastic way to warm up your problem-solving muscles and get comfortable with iterative approaches. Keep practicing, and you'll be seeing patterns everywhere!

Happy coding! ✨

Submission Details
Author Account: Vansh2710
Time Published: 2026-04-08 00:34:01

DEV Community