LeetCode Solution: 118. Pascal's Triangle

Demystifying Pascal's Triangle: A Beginner's Guide to LeetCode 118

Hey there, aspiring coders and problem-solvers! 👋 Today, we're going to dive into a classic and elegant LeetCode problem that's perfect for beginners: 118. Pascal's Triangle. Don't let the mathematical name intimidate you – this problem is a fantastic way to build your foundational algorithmic skills, especially with array manipulation and understanding patterns.

So, grab your favorite beverage, get comfortable, and let's unravel the beauty of Pascal's Triangle together!

---

The Problem: Building a Beautiful Triangle

The problem statement asks us to generate the first numRows of Pascal's Triangle.

What is Pascal's Triangle?
It's a triangular array of numbers where:

1. The first and last numbers in each row are always 1.
2. Every other number in a row is the sum of the two numbers directly above it from the previous row.

Let's look at an example to make this crystal clear:

Example 1:
Input: numRows = 5

Output:

[
     [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
]

See how 2 (in Row 2) is 1 + 1 from Row 1? And 3 (in Row 3) is 1 + 2 or 2 + 1 from Row 2? That's the core rule!

Constraints:

• 1 <= numRows <= 30 (This means we don't have to worry about super large inputs, which is nice for a beginner problem!)

---

The "Aha!" Moment: Finding the Pattern

Before jumping into code, let's think about how we'd build this triangle by hand.

1. Row 0: Always [1]
2. Row 1: Always [1, 1]
3. Row 2: We know it starts and ends with 1. The middle element? It's the sum of the elements above it from Row 1: 1 (left) + 1 (right) = 2. So, [1, 2, 1].
4. Row 3: Starts and ends with 1.
   • The first inner element: 1 (from Row 2, index 0) + 2 (from Row 2, index 1) = 3.
   • The second inner element: 2 (from Row 2, index 1) + 1 (from Row 2, index 2) = 3.
   • So, [1, 3, 3, 1].

Do you see the pattern now? Each new row depends entirely on the row immediately above it. This dependency is our key! We can generate the triangle row by row, using the previously generated row to construct the current one. This is a classic example of Dynamic Programming, where we solve subproblems (generating previous rows) to solve the main problem (generating the whole triangle).

---

The Approach: Building It Up

Here's our step-by-step strategy:

1. Initialize an empty list of lists (or vector of vectors in C++) called ans. This will hold our final Pascal's Triangle.

2. Iterate numRows times. Let's say our loop variable i represents the current row number we're trying to build (from 0 up to numRows - 1).

3. For each row i:

   • Create a temp list (or vector) to store the elements of the current row.
   • The current row i will always have i + 1 elements.
   • Initialize temp with i + 1 elements, setting all of them to 1. This conveniently handles the fact that the first and last elements of every row are always 1.

4. Calculate the inner elements:

   • If i is 0 or 1, the temp row is already correct ([1] or [1, 1]). We don't need to do anything else.
   • If i is greater than 1, we need to calculate the middle elements.
   • Loop j from 1 up to i - 1 (these are the indices of the inner elements).
   • For each temp[j], its value will be the sum of the element at ans[i-1][j-1] and ans[i-1][j].
     • ans[i-1] refers to the previous row that we've already generated and stored.
     • j-1 and j are the two elements directly above the current position j in the previous row.

5. Add the temp row to ans. After temp is fully constructed for the current row i, add it to our main ans list.

6. Return ans. After the loop finishes, ans will contain the complete Pascal's Triangle.

---

The Code: Bringing It to Life (C++)

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

        // Loop to generate each row, from row 0 up to numRows-1
        for (int i = 0; i < numRows; ++i) {
            // Create a new vector for the current row.
            // It will have (i + 1) elements.
            // We initialize all elements to 1, which covers the first and last elements.
            vector<int> temp(i + 1, 1);

            // If it's not the first or second row (rows 0 and 1 are just 1s)
            // we need to calculate the inner elements based on the previous row.
            if (i >= 2) {
                // Iterate from the second element (index 1) up to the second-to-last element (index i-1).
                // The first and last elements are already set to 1.
                for (int j = 1; j < i; ++j) {
                    // Each inner 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 overall triangle
            ans.push_back(temp);
        }
        // Return the final Pascal's Triangle
        return ans;
    }
};

---

Complexity Analysis

Understanding how efficient our solution is crucial in competitive programming!

• Time Complexity: O(numRows^2)

  • We have an outer loop that runs numRows times (once for each row).
  • Inside this loop, we have an inner loop that runs i times (where i is the current row number). The maximum value of i is numRows - 1.
  • So, in the worst case, we are doing operations proportional to 1 + 2 + ... + numRows. This sum is approximately (numRows * (numRows + 1)) / 2, which simplifies to O(numRows^2).

• Space Complexity: O(numRows^2)

  • We are storing the entire Pascal's Triangle.
  • The total number of elements in a triangle with numRows rows is also 1 + 2 + ... + numRows, which is O(numRows^2).
  • Since the problem asks us to return the entire triangle, this space is necessary to store the output.

---

Key Takeaways

• Pattern Recognition is King: Many algorithmic problems can be simplified by identifying repeating patterns or relationships between elements.
• Build It Incrementally: For problems involving sequences or structures like triangles, often the best approach is to build the solution piece by piece, using previously computed results. This is the essence of dynamic programming!
• Arrays and Nested Loops: This problem perfectly demonstrates how to use nested data structures (like vector<vector<int>> in C++) and nested loops to generate complex structures.
• Edge Cases: Handling the first few rows (Row 0 and Row 1) where the "sum of two numbers above" rule doesn't fully apply is important. Our initialization of temp with all 1s gracefully handles this!

---

Congratulations on tackling Pascal's Triangle! This problem is a fantastic stepping stone into more complex dynamic programming challenges. Keep practicing, and you'll be solving even tougher problems in no time!

Happy coding! ✨

---

Authored by Vansh2710 | Published: 2026-04-07 23:59:07