logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
Table Of Contents
13. Roman to Integer14. Longest Common Prefix20. Valid Parentheses26. Remove Duplicates from Sorted Array35. Search Insert Position69. Sqrt(x)70. Climbing Stairs88. Merge Sorted Array (In-Place)104. Maximum Depth of Binary Tree118. Pascal's Triangle121. Best Time to Buy and Sell Stock205. Isomorphic Strings242. Valid Anagram283. Move Zeroes345. Reverse Vowels of a String605. Can Place Flowers704. Binary Search796. Rotate String1071. Greatest Common Divisor of Strings1299. Replace Elements with Greatest Element on Right Side1431. Kids With the Greatest Number of Candies1614. Maximum Nesting Depth of the Parentheses1752. Check if Array Is Sorted and Rotated1768. Merge Strings Alternately1903. Largest Odd Number in String2965. Find Missing and Repeated Values
Code Scratch/leetcode/easy

118. Pascal's Triangle

5 min read
On this pageQuestion
QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-up

# Question

Given an integer numRows, return the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it.

# Solution

# Pattern

1D Dynamic Programming (State Transition) Build the current row based purely on the values of the immediately preceding row.

# How to Identify

  • The problem explicitly describes a generation process where the current state depends on the previous state.
  • The structure is a grid or triangle where elements at (r,c)(r, c)(r,c) depend on (r−1,c−1)(r-1, c-1)(r−1,c−1) and (r−1,c)(r-1, c)(r−1,c).

# Description

Step-by-step explanation:

  1. Validate input. If numRows is 0, return an empty list.
  2. Initialize the master list res to hold all the rows.
  3. Iterate i from 000 to numRows - 1. This loop represents the current row index.
  4. For each row i, create a new list row.
  5. Iterate j from 000 to i. This loop builds the elements of the current row.
  6. Boundary Condition: If j == 0 (first element) or j == i (last element), the value is strictly 111. Add 111 to the row.
  7. Internal Condition: For all other elements, fetch the previous row (res.get(i - 1)). The current value is the sum of the element directly above-left (j - 1) and above-right (j). Add this sum to the row.
  8. Once the inner loop finishes, add row to res.
  9. Return res.

# The Intuition

Think of this as building a brick wall. You cannot place a brick in the middle of a row until the two bricks directly beneath it (or "above" it, visually, in this problem) are securely in place. Because the rules of the wall strictly dictate that a brick's value is the sum of its two supporting bricks, you don't need any complex formulas. You just need to keep the very last row of bricks you built in your memory, and use it as the foundation to build the current row. The edges of the wall are always straight lines of 1s.

# Complexity

LabelWorstAverage
Time ComplexityO(N2)O(N^2)O(N2)O(N2)O(N^2)O(N2)
Space ComplexityO(1)O(1)O(1)O(1)O(1)O(1)

Note: NNN represents numRows.

# Time Complexity

The outer loop runs NNN times. The inner loop runs 1,2,3,…,N1, 2, 3, \dots, N1,2,3,…,N times. The total number of iterations is the sum of an arithmetic progression: N(N+1)2\frac{N(N+1)}{2}2N(N+1)​. This scales quadratically, making it strictly O(N2)O(N^2)O(N2).

# Space Complexity

The returned 2D array requires O(N2)O(N^2)O(N2) space to store the ≈N22\approx \frac{N^2}{2}≈2N2​ integers. However, auxiliary space (memory used beyond what is required to construct the output) is O(1)O(1)O(1), because we only create variables to hold the current row being built before appending it to the result list.

# Code

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List&lt;List&lt;Integer&gt;&gt; res = new ArrayList<>();
        if (numRows == 0) return res;
 
        for (int i = 0; i &lt; numRows; i++) {
            List&lt;Integer&gt; row = new ArrayList<&gt;();
            
            for (int j = 0; j &lt;= i; j++) {
                // The first and last elements of every row are always 1
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    // Other elements are the sum of the two elements directly above
                    List&lt;Integer&gt; prevRow = res.get(i - 1);
                    row.add(prevRow.get(j - 1) + prevRow.get(j));
                }
            }
            res.add(row);
        }
 
        return res;
    }
}

# Caveats

  • Integer Overflow: For standard LeetCode constraints (numRows up to 30), standard 32-bit int is fine. However, Pascal's Triangle values grow exponentially. By row 35, the middle elements will overflow Integer.MAX_VALUE. In a real system, you must switch to long or BigInteger for N &gt; 33.
  • Formulaic Approach: Do not use the combinatorial formula nCr=n!r!(n−r)!nCr = \frac{n!}{r!(n-r)!}nCr=r!(n−r)!n!​ to generate the entire triangle. Calculating factorials for every single cell independently takes O(N3)O(N^3)O(N3) time and is highly prone to overflow, making it vastly inferior to the O(N2)O(N^2)O(N2) addition method.

# Concepts to Think About

  • Space Optimization: If the problem only asked you to return the last row (Pascal's Triangle II), you do not need to store the entire 2D triangle. You can compute the rows in-place using a single 1D array of size NNN, updating it from back-to-front to achieve O(N)O(N)O(N) space.
  • Binomial Expansion: The kkk-th row of Pascal's triangle represents the coefficients of the binomial expansion (x+y)k(x+y)^k(x+y)k.
  • Combinatorics: The element at row nnn and column kkk (0-indexed) is exactly equal to (nk)\binom{n}{k}(kn​) (n choose k).

# Logical Follow-up

Question: Given an integer rowIndex, return only the kkk-th row of Pascal's triangle using strictly O(k)O(k)O(k) extra space. (LeetCode 119: Pascal's Triangle II)

Solution: We use a single 1D array/list initialized with 1s. We iterate kkk times. In each iteration, we traverse the array backwards from j = i - 1 down to 1, updating the array in place: row[j] = row[j] + row[j-1]. Traversing backwards ensures we don't overwrite the row[j-1] value before we need it to calculate row[j]. This achieves O(k2)O(k^2)O(k2) time and O(k)O(k)O(k) space.

Question: Can you get the kkk-th row in O(k)O(k)O(k) time?

Solution: Yes, by using the mathematical property of combinations. The elements in row nnn are (n0),(n1),…,(nn)\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}(0n​),(1n​),…,(nn​). We can calculate the next element from the previous element in O(1)O(1)O(1) time using the relation: C(n,k)=C(n,k−1)×n−k+1kC(n, k) = C(n, k-1) \times \frac{n - k + 1}{k}C(n,k)=C(n,k−1)×kn−k+1​. We start with 111, and apply this formula to generate the row in exactly O(k)O(k)O(k) time and O(k)O(k)O(k) space.

←Previous104. Maximum Depth of Binary TreeNext→121. Best Time to Buy and Sell Stock

On this page

QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-up