0735EasyArrayDynamic Programming

Row Of The Drop Board

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A drop board is laid out as a triangle of cells. The top row is row 0 and holds a single cell containing 1.

Each row below has one cell more than the row above it. The cell at each end of a row holds 1, and every other cell holds the total of its two neighbours in the row above.

Given level, return the contents of row level, read from left to right.

Examples

Example 1

Input: level = 4
Output: [1, 4, 6, 4, 1]

Row 3 reads 1, 3, 3, 1. Row 4 is one cell longer, holds 1 at each end, and its inner cells hold 1 + 3 = 4, 3 + 3 = 6 and 3 + 1 = 4.

Example 2

Input: level = 6
Output: [1, 6, 15, 20, 15, 6, 1]

Row 5 reads 1, 5, 10, 10, 5, 1, so the inner cells of row 6 hold 6, 15, 20, 15 and 6, with 1 at each end.

Example 3

Input: level = 8
Output: [1, 8, 28, 56, 70, 56, 28, 8, 1]

Row 7 reads 1, 7, 21, 35, 35, 21, 7, 1, and totalling its neighbouring pairs gives the inner cells 8, 28, 56, 70, 56, 28 and 8, with 1 at each end.

Constraints

0 <= level <= 33
Every number in the answer fits in a signed 32-bit integer.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def board_row(level: int) -> list[int]:

Java

public List<Integer> boardRow(int level)

The intended approach

Time O(level^2): each of the level steps down walks the row it has built so far.Space O(1) beyond the row that is returned.

A row only ever needs the row directly above it, so one list is enough. Start from the top row, and for each step down append a `1` to make the list one cell longer, then walk the inner cells from the right end towards the left, adding the cell on the left into each one. Going right to left means every cell still holds its value from the row above when the cell to its right needs it, and the two end cells are left at `1`.

Pythonentry point: board_row

def board_row(level):
    # Keep one row and grow it in place.  Appending a 1 makes room for the new row,
    # and updating the cells from the right end inwards means each cell is still
    # holding its old value when the cell to its right reads it.
    # Time O(level^2); space O(1) beyond the row that is returned.
    row = [1]
    for width in range(1, level + 1):
        row.append(1)
        for k in range(width - 1, 0, -1):
            row[k] += row[k - 1]
    return row

The obvious version

Price each cell on its own from factorials: the cell at position k of row n is the factorial of n divided by the factorials of k and of n - k, using whole-number division. Builds no rows at all.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_board_row(level):
    def factorial(n):
        out = 1
        for i in range(2, n + 1):
            out *= i
        return out

    top = factorial(level)
    return [top // (factorial(k) * factorial(level - k)) for k in range(level + 1)]

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in