Gravity Grid k-in-a-Row
Two players, B and R, play on the lattice columns of the upper half-plane. Columns are indexed by all integers (..., -1, 0, 1, ...). B moves first; players alternate. A move is a column index: the new piece enters at the BOTTOM (row 0) of that column and pushes every existing piece in that column UP by one row (the opposite of normal Connect-Four gravity).
Given an integer k >= 1 and the list of columns played (in order, B then R alternating), return the sorted list of distinct colors that have achieved a win. A color wins if it has k consecutive same-color pieces in a single row (horizontal, consecutive integer columns at the same row index) OR in a single column (vertical, consecutive rows). Both colors can win simultaneously.
Complete: ``` find_winners(k: int, moves: List[int]) -> List[str] ``` Return the winners as a sorted list, e.g. [], ["B"], or ["B", "R"]. Example: k = 3, moves = [0, 5, 0, 5, 0] -> B drops three pieces into column 0 (rows 0,1,2 all B after the pushes), so ["B"].
Hints
- New pieces enter at the bottom and shove the column upward, so model each column bottom-up and insert at index 0.
- Check vertical runs within a column and horizontal runs across consecutive integer columns at the same row; both colors can win.
Worked Solution
Store each column as a list of colors from the bottom up; inserting a piece at the bottom is insert(0, color), which shifts existing pieces up (their row indices increase by one), matching the rule. Keep columns in a dict keyed by integer index so negative and sparse columns are free.
After replaying the moves, scan for k-runs. Vertical: within each column's bottom-up list, find runs of equal colors of length >= k. Horizontal: bucket cells by row index, then within each row scan consecutive integer columns for equal-color runs of length >= k. Collect every color that reaches a run into a set.
```python def find_winners(k, moves): from collections import defaultdict cols = defaultdict(list) # col -> [bottom, ..., top] for i, c in enumerate(moves): color = 'B' if i % 2 == 0 else 'R' cols[c].insert(0, color) # bottom insert pushes the column up winners = set() # vertical runs for c, stack in cols.items(): if k == 1 and stack: winners.add(stack[0]) run = 1 for r in range(1, len(stack)): run = run + 1 if stack[r] == stack[r-1] else 1 if run >= k: winners.add(stack[r]) # horizontal runs: group cells by row, scan consecutive columns rows = defaultdict(dict) for c, stack in cols.items(): for r, color in enumerate(stack): rows[r][c] = color for r, rowmap in rows.items(): for c, color in rowmap.items(): if rowmap.get(c-1) == color: continue # not the start of a run run, cc = 1, c while rowmap.get(cc+1) == color: run += 1; cc += 1 if run >= k: winners.add(color) return sorted(winners) ```
The efficient version only re-checks around the column just played (O(k) per row touched). Complexity here is O(total pieces) per full scan.
Intuition
The board is sparse and unbounded in column index, so a dict of bottom-up stacks captures it exactly; the bottom-insert rule is just insert(0, ...). Winning is a k-length same-color run along a row or a column.