LeetCode Solution: 118. Pascal's Triangle

Diving into Pascal's Triangle: A Beginner-Friendly LeetCode Journey

Hey awesome developers! 👋 Vansh here, ready to unravel another classic LeetCode puzzle with you. Today, we're taking a delightful dive into Pascal's Triangle (Problem 118). Don't worry if it sounds intimidating; it's a beautiful mathematical pattern that's surprisingly straightforward to generate once you spot the trick!

Get ready to flex those problem-solving muscles and see how a simple observation can lead to an elegant solution.

---

The Problem: Unpacking Pascal's Triangle

What is it?
Pascal's Triangle is a fascinating geometric arrangement of numbers where each number is the sum of the two numbers directly above it. It starts with a single '1' at the top. Think of it like a pyramid or a Christmas tree made of numbers!

Here's how it looks:

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   ... and so on!

The Task:
Given an integer numRows, your goal is to return the first numRows of Pascal's triangle. The output should be a vector of vectors (or a list of lists in Python) where each inner vector represents a row of the triangle.

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

Constraints:
1 <= numRows <= 30 (This means numRows will always be at least 1, and won't be excessively large, so performance shouldn't be a huge issue with a direct approach).

---

The Intuition: Building Block by Block

When you look at Pascal's Triangle, a few things immediately jump out:

1. The Edges are Always 1: Every row starts and ends with a 1. This is a constant.
2. The Core Rule: Any number inside a row (not at the very beginning or end) is the sum of the two numbers directly above it from the previous row.
   • For example, in 1 4 6 4 1, the 6 is 3 + 3 from the row above (1 3 3 1).
3. Growing Rows: Each row i has i+1 elements (Row 0 has 1 element, Row 1 has 2 elements, and so on).

This immediately suggests a row-by-row construction. We can build the triangle one row at a time, using the previously generated row to calculate the current one. This is a classic example of Dynamic Programming, where we solve subproblems (generating previous rows) to build up the final solution.

---

The Approach: Step-by-Step Construction

Let's break down how we can implement this intuition:

1. Initialize Result: We'll need a vector<vector<int>> (let's call it ans) to store all the rows of our Pascal's Triangle.

2. Iterate for Each Row: We'll use an outer loop that runs numRows times. Let's say i is our current row index (starting from 0).

3. Create Current Row: For each i, we need to create a vector<int> (let's call it temp) that will represent the i-th row. This temp row will have i + 1 elements. A neat trick is to initialize all elements of temp to 1 from the start, as the first and last elements are always 1.

*   For `i = 0`, `temp` will be `[1]`.
*   For `i = 1`, `temp` will be `[1, 1]`.
*   For `i = 2`, `temp` will be `[1, 1, 1]` (we'll update the middle '1' later).

1. Calculate Inner Elements: Now, for any row i that has more than two elements (i.e., i >= 2), we need to calculate the values between the starting and ending 1s.

   • We'll use an inner loop, let's say with index j, that goes from 1 up to i-1. (Remember, j=0 is the first element and j=i is the last, both of which are already 1).
   • The core formula: temp[j] = ans[i-1][j-1] + ans[i-1][j]. This means the current element temp[j] is the sum of the element directly above it (ans[i-1][j]) and the element to its top-left (ans[i-1][j-1]).

2. Add to Result: After filling temp for the current row i, add temp to our ans vector.

3. Return: Once the outer loop finishes, ans will contain all numRows of Pascal's Triangle. Return ans.

Let's trace it for numRows = 3:

• ans = []
• i = 0 (Row 1):
  • temp is created: [1] (size 0+1).
  • Inner loop j=1 to 0-1 (doesn't run).
  • ans.push_back([1]). Now ans = [[1]].
• i = 1 (Row 2):
  • temp is created: [1, 1] (size 1+1).
  • Inner loop j=1 to 1-1 (doesn't run).
  • ans.push_back([1, 1]). Now ans = [[1], [1, 1]].
• i = 2 (Row 3):
  • temp is created: [1, 1, 1] (size 2+1).
  • Inner loop j=1 to 2-1 (i.e., j=1):
    • temp[1] = ans[i-1][j-1] + ans[i-1][j]
    • temp[1] = ans[1][0] + ans[1][1]
    • temp[1] = 1 + 1 = 2.
  • temp is now [1, 2, 1].
  • ans.push_back([1, 2, 1]). Now ans = [[1], [1, 1], [1, 2, 1]].

The loops finish, and we return ans. Perfect!

---

The Code

Here's the C++ implementation following our approach:

#include <vector> // Don't forget to include necessary headers!

class Solution {
public:
    std::vector<std::vector<int>> generate(int numRows) {
        std::vector<std::vector<int>> ans;

        // Iterate through each row we need to generate
        for (int i = 0; i < numRows; ++i) {
            // Each row 'i' will have 'i+1' elements.
            // Initialize the row with 1s. The first and last elements are always 1.
            std::vector<int> temp(i + 1, 1);

            // Calculate the inner elements for rows with at least 3 elements (i.e., i >= 2)
            // For i=0 (row 1), temp is {1}. Loop j=1 to -1, doesn't run.
            // For i=1 (row 2), temp is {1,1}. Loop j=1 to 0, doesn't run.
            // For i=2 (row 3), temp is {1,?,1}. Loop j=1 to 1. temp[1] calculated.
            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 completed row to our answer
            ans.push_back(temp);
        }
        return ans;
    }
};

---

Time & Space 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 create a temp vector of size i+1.
  • Then, we have an inner loop that runs i-1 times (to fill the inner elements).
  • The total number of operations roughly corresponds to the sum of elements generated: 1 + 2 + 3 + ... + numRows. This sum is equal to numRows * (numRows + 1) / 2, which simplifies to O(numRows^2).

• Space Complexity: O(numRows^2)

  • We are storing the entire Pascal's Triangle in our ans vector.
  • The total number of elements stored is 1 + 2 + 3 + ... + numRows, which again is numRows * (numRows + 1) / 2.
  • Therefore, the space complexity is O(numRows^2).

Given the constraint 1 <= numRows <= 30, an O(numRows^2) solution is perfectly fine and highly efficient for this problem!

---

Key Takeaways

1. Pattern Recognition: Many LeetCode problems (especially those involving sequences or grids) can be solved by first identifying the underlying pattern or recurrence relation. Pascal's Triangle has a very clear one!
2. Dynamic Programming (DP): When solving a problem involves using results from previously solved smaller subproblems, think DP! Here, each row depends on the previous row.
3. Edge Cases: Always consider the smallest inputs. For numRows=1 or numRows=2, our inner loop for (int j = 1; j < i; ++j) correctly doesn't run, as these rows only have 1s.
4. Clarity over Micro-Optimizations: For constraints like numRows <= 30, a clear, readable, and correct solution is far more valuable than trying to squeeze out every last bit of performance.

---

I hope this walkthrough made Pascal's Triangle as clear as crystal! Understanding these fundamental patterns and approaches is a crucial step in your competitive programming journey.

Happy coding, and see you in the next one!

---

Author: Vansh2710
Published: 2026-04-08 00:04:59