0134EasyArrayDynamic Programming

Peg Board Path Counts

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 toy factory tests bead boards. A board is a triangular grid of pegs: the top row holds one peg, and each row below holds one peg more than the row above it, offset so that a bead resting on a peg falls onto one of the two pegs directly beneath it. A bead always starts on the single peg of the top row, and at every peg it deflects either left or right.

Number the rows 1 through rows from the top and, inside row r, number the pegs 1 through r from the left. For a board of rows rows, return a list whose r-th entry lists, for each peg of row r in left-to-right order, the number of distinct deflection sequences that land a bead on that peg.

The two outer pegs of any row are reachable by exactly one sequence, since every deflection has to go the same way. Every inner peg can be reached from the two pegs above it, so its count is the sum of their counts.

Examples

Example 1

Input: rows = 4
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]

Row 3 is built from row 2: its middle peg collects the beads from both pegs above, so it counts 2, while the outer pegs stay at 1. Row 4 repeats the rule.

Example 2

Input: rows = 6
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]

Each row is derived from the previous one by summing adjacent counts and capping both ends with 1.

Example 3

Input: rows = 2
Output: [[1], [1, 1]]

A two-row board has one peg on top and two below it, each reachable by a single deflection.

Constraints

1 <= rows <= 30

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 bead_path_counts(rows: int) -> list[list[int]]:

Java

public List<List<Integer>> beadPathCounts(int rows)

The intended approach

Time O(rows^2)Space O(rows^2) for the returned board, O(rows) beyond it

Build the rows top down. Start each row filled with ones, which already settles the two outer pegs, then overwrite the inner pegs with the sum of the two counts above them taken from the row just finished. Reading the previous row rather than the row under construction is what keeps the sums honest.

Pythonentry point: bead_path_counts

def bead_path_counts(rows):
    board = []
    previous = []
    for depth in range(rows):
        current = [1] * (depth + 1)
        for slot in range(1, depth):
            current[slot] = previous[slot - 1] + previous[slot]
        board.append(current)
        previous = current
    return board

The obvious version

Count each peg independently by enumerating which of the `r-1` deflections went left, using combinations. No row is ever derived from another, so the recurrence is never used.

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_bead_path_counts(rows):
    from itertools import combinations

    def routes(depth, slot):
        # a bead reaching peg `slot` of row `depth + 1` deflected right on exactly
        # `slot` of its `depth` deflections; count the ways to choose which ones
        return sum(1 for _ in combinations(range(depth), slot))

    return [[routes(depth, slot) for slot in range(depth + 1)] for depth in range(rows)]

How this problem was checked

Reference solution executed against 7 test cases — 7 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