Assign Each Person the Nearest Cake in a One-Dimensional Row
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
Input: row = [1, 1, 0, 2]
Output: [3, 3]
```
Both people share the only cake.
**Example 3**
```text
Input: row = [0, 2, 1, 2, 0]
Output: [1]
```
The cakes at 1 and 3 are both 1 away, and the smaller index wins.
Overview: Given a one-dimensional row marking empty spots, people and cakes, return for each person the index of the nearest cake, breaking ties toward the smaller index. It tests linear scanning techniques for nearest-neighbor queries on a line and careful handling of ties and boundaries.
People and cakes stand in a single row of positions, described by an integer array `row` whose values are `0`, `1` or `2`:
- `row[i] == 0` means position `i` is empty.
- `row[i] == 1` means a person stands at position `i`.
- `row[i] == 2` means a cake is at position `i`.
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.
Assign every person the cake closest to them, and return the index of each person's assigned cake. 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.
(The original version of this question asks for the closest distance between a person and a cake; that answer is the smallest of the distances between each person and their assigned cake.)
Every returned index is less than `10^5`, so all values fit in a signed 32-bit integer.
**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 = [0, 2, 1, 2, 0]`
Output: `[1]`
The cakes at 1 and 3 are both 1 away from the person at 2, and the smaller index wins.
**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`.
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
Input: ([1, 2],)
Expected Output: [1]
Explanation: Minimum length: one person at 0, the only cake is at the last index 1.
Input: ([2, 1],)
Expected Output: [0]
Explanation: Minimum length: the only cake is at index 0.
Hints
- Distance ignores whatever stands between two positions, so only the cake positions and the person's own position matter.
- Think about which cakes on each side of a person could possibly be the closest one.
- When two cakes are the same distance away, the rule fixes the answer: the smaller index wins.