Assign Each Person the Nearest Cake in a One-Dimensional Row

People and cakes stand in a single row of positions, described by an integer array whose values are 0, 1 or 2. The original question asks for the closest distance between a person and a cake; the follow-up asks you to assign every person the cake closest to them. Implement the follow-up: for each person, return the position of their nearest cake. The original answer is then the smallest of those distances.

Function Signature

def nearest_cakes(row: list[int]) -> list[int]:

Rules

• row[i] == 0 means position i is empty, row[i] == 1 means a person stands there, and row[i] == 2 means a cake is there. Each position holds at most one thing.
• The distance between positions i and j is abs(i - j). Empty positions and other people do not block anyone.
• Several people can be assigned the same cake; cakes are not used up.
• If two cakes are equally close to a person, assign the one with the smaller index.
• Return one cake index per person, ordered by the person's position from left to right.

Constraints

• 2 <= len(row) <= 10^5
• Every row[i] is 0, 1 or 2.
• row contains at least one 1 and at least one 2.

Examples

Example 1

Input: row = [2, 1, 0, 1, 0, 0, 2, 1]
Output: [0, 0, 6]

The people stand at positions 1, 3 and 7, and the cakes are at 0 and 6. The person at 3 is 3 away from both cakes, so the tie goes to index 0. The closest person-cake distance in this row is 1.

Example 2

Input: row = [1, 1, 0, 2]
Output: [3, 3]

Both people share the only cake.

Example 3

Input: row = [0, 2, 1, 2, 0]
Output: [1]

The cakes at 1 and 3 are both 1 away, and the smaller index wins.