Pascal's Triangle
Real-world version: Peg Board Path CountsThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def bead_path_counts(rows: int) -> list[list[int]]:public List<List<Integer>> beadPathCounts(int rows)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 7 test cases: 7 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's