Pascal's Triangle — Part I

Given two integers r and c, return the value at the rth row and cth column (1-indexed) in Pascal's Triangle.

• The first row contains a single element 1.
• Each row has one more element than the previous row.
• Every row starts and ends with 1.
• Every interior element equals the sum of the two elements directly above it:

Pascal[r][c] = Pascal[r−1][c−1] + Pascal[r−1][c]

Practice here

Optimal Solution — nCr Formula#

Intuition:

If you write out Pascal's Triangle and look at row r (1-indexed), the elements are exactly the binomial coefficients:

Row 1:  C(0,0)
Row 2:  C(1,0)  C(1,1)
Row 3:  C(2,0)  C(2,1)  C(2,2)
Row 4:  C(3,0)  C(3,1)  C(3,2)  C(3,3)

So the element at row r, column c is:

Pascal[r][c] = C(r−1, c−1)

This means we never need to build the triangle — just compute one binomial coefficient directly.

How nCr is computed:

The naive formula n! / (r! * (n-r)!) overflows quickly. Instead, use the multiplicative form:

C(n, r) = (n * (n-1) * ... * (n-r+1)) / (r * (r-1) * ... * 1)
         = (n/1) * ((n-1)/2) * ((n-2)/3) * ... * ((n-r+1)/r)

At each step i (0-indexed), multiply by (n - i) then divide by (i + 1). Because binomial coefficients are always integers, each intermediate division is exact — no floating point needed.

class Solution {
public:
    int computeNCR(int n, int r) {
        long long ans = 1;
        for (int i = 0; i < r; i++) {
            ans *= (n - i);
            ans /= (i + 1);
        }
        return ans;
    }

    int pascalTriangleI(int r, int c) {
        return computeNCR(r - 1, c - 1);
    }
};

Time Complexity: O(c) — only c−1 iterations needed

Space Complexity: O(1)