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
3. 3Sum4. 4SumMaximum SubarrayLeaders in an ArrayMajority ElementNext PermutationGet specific element from Pascal's TrianglePascal's Triangle II (Row Generation)Generate Pascal's Triangle (Full)Spiral Matrix TraversalRearrange Array Elements by SignRotate ImageSort Colors (Dutch National Flag)Two Sum
Code Scratch/take u forward/arrays/faqs medium

Get specific element from Pascal's Triangle

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

# Question

Given two integers rrr and ccc, return the value at the rrr-th row and ccc-th column (1-indexed) in Pascal's Triangle.

# Solution

# Pattern

Combinatorics (nCrnCrnCr) The value at any coordinate (r,c)(r, c)(r,c) in Pascal's triangle mathematically maps perfectly to the combination formula (nk)\binom{n}{k}(kn​) (n choose k), where n=r−1n = r - 1n=r−1 and k=c−1k = c - 1k=c−1. We calculate this iteratively to achieve O(k)O(k)O(k) time and O(1)O(1)O(1) space.

# How to Identify

  • The problem asks for a single specific element in Pascal's triangle, or a single row.
  • Generating the triangle row-by-row via dynamic programming takes O(r2)O(r^2)O(r2) time/space, which is massively inefficient for isolated queries.
  • The need to jump directly to an answer implies a closed-form math formula.

# Description

Step-by-step explanation:

  1. Index Conversion: The prompt uses 1-based indexing. Combinatorics uses 0-based indexing. The top of the triangle is (00)\binom{0}{0}(00​). We map n=r−1n = r - 1n=r−1 and k=c−1k = c - 1k=c−1.
  2. Symmetry Optimization: Pascal's triangle is horizontally symmetrical. Mathematically, (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}(kn​)=(n−kn​). If kkk is greater than half of nnn, we set k=n−kk = n - kk=n−k. This bounds our maximum iterations.
  3. Iterative Expansion: The combination formula is n!k!(n−k)!\frac{n!}{k!(n-k)!}k!(n−k)!n!​. Calculating factorials directly causes instant integer overflow. Instead, we expand the terms iteratively: n1×n−12×n−23…n−k+1k\frac{n}{1} \times \frac{n-1}{2} \times \frac{n-2}{3} \dots \frac{n-k+1}{k}1n​×2n−1​×3n−2​…kn−k+1​.
  4. Initialize a running total res to 1. (Must use a 64-bit integer / long).
  5. Loop iii from 000 to k−1k-1k−1.
  6. In each iteration, multiply res by (n−i)(n - i)(n−i) and then immediately divide it by (i+1)(i + 1)(i+1).
  7. Cast the result back to a 32-bit integer and return.

# The Intuition

Why multiply and divide iteratively? If you want to pick 3 people from a group of 10 ((103)\binom{10}{3}(310​)), you have 10 choices for the first, 9 for the second, and 8 for the third. That is 10×9×810 \times 9 \times 810×9×8. Because the order you picked them doesn't matter, you divide out the permutations of those 3 people (3×2×13 \times 2 \times 13×2×1). Instead of calculating 720/6720 / 6720/6, we pair the operations: (10/1)×(9/2)×(8/3)(10 / 1) \times (9 / 2) \times (8 / 3)(10/1)×(9/2)×(8/3). By multiplying and dividing at every single step, we keep the running number as small as mathematically possible to avoid memory overflow limits, while guaranteeing that the division will always result in a clean whole number at every step.

# Complexity

LabelWorstAverage
Time ComplexityO(c)O(c)O(c)O(c)O(c)O(c)
Space ComplexityO(1)O(1)O(1)O(1)O(1)O(1)

Note: With symmetry optimization, worst-case time is tightly bounded to O(min⁡(c,r−c))O(\min(c, r-c))O(min(c,r−c)).

# Time Complexity

The loop runs exactly kkk times. Because of the symmetry optimization, k≤n/2k \le n/2k≤n/2. The time scales linearly with the column index (or distance from the nearest edge).

# Space Complexity

Only a few primitive variables (res, i, n, k) are allocated. Auxiliary space is strictly O(1)O(1)O(1).

# Code

class Solution {
    public int pascalTriangleI(int r, int c) {
        // Pascal(r, c) == (r-1) Choose (c-1)
        return (int) nCr(r - 1, c - 1);
    }
 
    private long nCr(int n, int k) {
        // Optimization: C(n, k) == C(n, n-k)
        if (k > n - k) {
            k = n - k;
        }
 
        // Use long to prevent silent overflow during multiplication
        long res = 1;
        for (int i = 0; i < k; i++) {
            res *= (n - i);
            res /= (i + 1);
        }
        
        return res;
    }
}

# Caveats

  • Integer Overflow Trap: The final answer might easily fit in a 32-bit int, but the intermediate step res * (n - i) can vastly exceed 2,147,483,647 before the division operation brings it back down. You must use a 64-bit long for the running product.
  • Order of Operations: In the loop, you must multiply before you divide. res = res * (n - i) / (i + 1) works. If you do res = res * ((n - i) / (i + 1)), integer division truncation will destroy the math (e.g., 9/29 / 29/2 evaluates to 444 instead of 4.54.54.5, ruining the product).

# Concepts to Think About

  • Modular Arithmetic Limits: If a problem requires you to return the combination modulo 109+710^9 + 7109+7, this iterative approach fails because you cannot easily divide under modulo. You must instead calculate the Modular Multiplicative Inverse of the denominator using Fermat's Little Theorem.
  • Factorial Array DP: If you need to answer many nCrnCrnCr queries rapidly, you can precompute an array of factorials (and their modular inverses) in O(N)O(N)O(N) time, allowing you to answer any (nk)\binom{n}{k}(kn​) query in O(1)O(1)O(1) time.
  • Symmetry Property: Pascal's Triangle is a mirror image of itself. Mathematically: (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}(kn​)=(n−kn​) In your code, checking if (k > n / 2) k = n - k; can cut your loop iterations in half and significantly reduce the risk of intermediate overflow.
  • DP vs. Math Trade-offs:
    • Use DP (O(r2)\text{O}(r^2)O(r2)) if you need to return the entire triangle, as you have to touch every element anyway.
    • Use Math (O(c)\text{O}(c)O(c)) if you only need one element or a single row, as it is significantly more space and time-efficient.
  • The Row Generation "Trick": There is a linear relationship between adjacent elements in a row. If you have the value of (nk)\binom{n}{k}(kn​), you can calculate (nk+1)\binom{n}{k+1}(k+1n​) in O(1)\text{O}(1)O(1) time using the formula: (nk+1)=(nk)×n−kk+1\binom{n}{k+1} = \binom{n}{k} \times \frac{n-k}{k+1}(k+1n​)=(kn​)×k+1n−k​ This allows you to generate an entire row in O(n)\text{O}(n)O(n) time and O(n)\text{O}(n)O(n) space.

# Logical Follow-up

Question: Generate the entire kkk-th row of Pascal's triangle (0-indexed) using only O(k)O(k)O(k) extra space and O(k)O(k)O(k) time.

Solution: We use the exact same combinatorial logic. Instead of finding a single element, we leverage the fact that the next element in a row can be derived directly from the previous element in O(1)O(1)O(1) time. The mathematical relationship between adjacent elements is: Current=Previous×n−i+1iCurrent = Previous \times \frac{n - i + 1}{i}Current=Previous×in−i+1​. Initialize an array res[0] = 1. Then, loop iii from 111 to kkk, applying res[i] = res[i-1] * (k - i + 1) / i. Return the array. This generates the entire row efficiently without calculating combinations from scratch for every cell.

←PreviousNext PermutationNext→Pascal's Triangle II (Row Generation)

On this page

QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-up