Pascal's Triangle I

Easy

One binomial coefficient, computed iteratively

Problem

Given two integers r and c, return the value at the r^th row and c^th column (1-indexed) in a Pascal's Triangle. 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. For all interior elements (i.e., not at the ends), the value at position (r, c) is computed as the sum of the two elements directly above it from the previous row: Pascal[r][c]=Pascal[r−1][c−1]+Pascal[r−1][c] where indexing is 1-based

In simple words

Each number is the sum of the two numbers sitting above it in the triangle.

The idea

The value at row r, column c is the binomial coefficient C(r-1, c-1). Building it by multiplying and dividing term by term keeps the intermediate numbers small and avoids computing factorials that overflow immediately.

The trick

Value = C(r-1, c-1); multiply and divide as you go rather than using factorials.
Computing one entry is O(c); the whole row is O(c) too.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(c)spaceO(1)

1// value at row r, col c (1-indexed) = C(r-1, c-1)2res = 13for i in 0..c-2:4  res = res * (r - 1 - i) / (i + 1)5return res

Input

array: [4, 2]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: row = 1
Output:: [1]
Explanation:: The first row is just [1].

Example 2

Input:: row = 4
Output:: [1, 3, 3, 1]
Explanation:: Each value is the sum of the two above it.

Example 3

Input:: row = 5
Output:: [1, 4, 6, 4, 1]
Explanation:: Row 5 is 1,4,6,4,1.

Constraints

1 <= r, c <= 30
c <= r
All values will fit inside a 32-bit integer.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.