Nearest Person-to-Cake Distance and Greedy Closest-Pair Assignment Total
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given an array `A` of length `n` in which every element is `0` (an empty spot), `1` (a person) or `2` (a cake). The distance between positions `i` and `j` is `|i - j|`. Answer two questions about `A`:
1. What is the minimum distance between any person and any cake?
2. The follow-up: cakes are handed out greedily. At each step, the person and the cake that are closest to each other among everyone and everything still unassigned are paired, and both are removed. This repeats until no person or no cake remains. What is the total distance of all the pairs made?
The greedy process is not a search for the assignment with the smallest total; it applies the closest-pair rule step by step, even when a different assignment would cost less. The report gives the follow-up in a single line and guarantees that the closest pair is unique at every step; this version fixes the exact rule in Rules below.
### Function Signature
```python
def person_cake_distances(A: list[int]) -> list[int]:
```
### Rules
- Return `[min_distance, greedy_total]`.
- `min_distance` is the smallest `|i - j|` over every `i` with `A[i] == 1` and every `j` with `A[j] == 2`. If `A` contains no person or no cake, `min_distance` is `-1`.
- `greedy_total`: start with every person and every cake unassigned. While at least one person and at least one cake are unassigned, take the unassigned pair (person at `i`, cake at `j`) with the smallest `|i - j|`, add `|i - j|` to the total, and mark both as assigned. When the numbers of people and cakes differ, the extra ones stay unassigned and add nothing. If `A` contains no person or no cake, `greedy_total` is `0`.
- Nothing ever blocks a pairing: the distance between a person and a cake depends only on their positions, whatever empty spots or already assigned people and cakes lie between them.
### Constraints
- `1 <= n <= 10^5`
- Every `A[i]` is `0`, `1` or `2`.
- At every step of the greedy process, exactly one unassigned (person, cake) pair has the smallest distance. Every test input satisfies this guarantee, so the result is unique.
- `greedy_total` is at most `floor(n / 2) * (n - 1)`, which is below `5 * 10^9` and can exceed `2^31 - 1`; use a 64-bit integer in a fixed-width language.
### Examples
**Example 1**
```text
Input: A = [1, 0, 2, 0, 0, 1, 2, 0, 1]
Output: [1, 3]
```
People stand at 0, 5 and 8; cakes are at 2 and 6. The closest pair is the person at 5 and the cake at 6 (distance 1), which is also the answer to the first question. With them removed, the person at 0 and the cake at 2 (distance 2) are closer than the person at 8 and the cake at 2 (distance 6), so they are paired next. No cake is left for the person at 8. Total: `1 + 2 = 3`.
**Example 2**
```text
Input: A = [2, 0, 1, 2, 0, 0, 1]
Output: [1, 7]
```
Cakes are at 0 and 3; people stand at 2 and 6. The closest pair is the person at 2 and the cake at 3 (distance 1), so the person at 6 then takes the cake at 0 (distance 6), for a total of 7. Pairing the person at 2 with the cake at 0 and the person at 6 with the cake at 3 would cost only `2 + 3 = 5`, but the greedy rule does not look ahead.
**Example 3**
```text
Input: A = [0, 1, 0, 1]
Output: [-1, 0]
```
There is no cake, so no person-to-cake distance exists and nothing is assigned.
Overview: A coding question on an array whose cells are empty, a person or a cake: find the smallest index distance between any person and any cake, then simulate a greedy follow-up that repeatedly pairs the closest remaining person and cake and returns the total distance of all pairs. It tests array scanning and efficient simulation of a greedy rule.
Read the full Snowflake Software Engineer interview experience this question came from
You are given an array `A` of length `n` in which every element is `0` (an empty spot), `1` (a person) or `2` (a cake). The distance between positions `i` and `j` is `|i - j|`. Answer two questions about `A` and return the answers as a list `[min_distance, greedy_total]`.
1. `min_distance` is the smallest `|i - j|` over every `i` with `A[i] == 1` and every `j` with `A[j] == 2`. If `A` contains no person or no cake, `min_distance` is `-1`.
2. `greedy_total` comes from handing out cakes greedily. Start with every person and every cake unassigned. While at least one person and at least one cake are unassigned, take the unassigned pair (person at `i`, cake at `j`) with the smallest `|i - j|`, add `|i - j|` to the total, and mark both as assigned. When the numbers of people and cakes differ, the extra ones stay unassigned and add nothing. If `A` contains no person or no cake, `greedy_total` is `0`.
The greedy process is not a search for the assignment with the smallest total: it applies the closest-pair rule step by step, even when a different assignment would cost less. Nothing ever blocks a pairing: the distance between a person and a cake depends only on their positions, whatever empty spots or already assigned people and cakes lie between them. Every input guarantees that the closest unassigned pair is unique at every step, so the result is unique.
`greedy_total` can exceed `2^31 - 1` (it stays below `5 * 10^9`), so use a 64-bit integer: `long` in Java, `long long` in C++.
**Example 1**
```text
Input: A = [1, 0, 2, 0, 0, 1, 2, 0, 1]
Output: [1, 3]
```
People stand at 0, 5 and 8; cakes are at 2 and 6. The closest pair is the person at 5 and the cake at 6 (distance 1), which is also the answer to the first question. With them removed, the person at 0 and the cake at 2 (distance 2) are closer than the person at 8 and the cake at 2 (distance 6), so they are paired next. No cake is left for the person at 8. Total: `1 + 2 = 3`.
**Example 2**
```text
Input: A = [2, 0, 1, 2, 0, 0, 1]
Output: [1, 7]
```
Cakes are at 0 and 3; people stand at 2 and 6. The closest pair is the person at 2 and the cake at 3 (distance 1), so the person at 6 then takes the cake at 0 (distance 6), for a total of 7. Pairing the person at 2 with the cake at 0 and the person at 6 with the cake at 3 would cost only `2 + 3 = 5`, but the greedy rule does not look ahead.
**Constraints**
- `1 <= n <= 10^5`
- Every `A[i]` is `0`, `1` or `2`.
- At every step of the greedy process, exactly one unassigned (person, cake) pair has the smallest distance. Every test input satisfies this guarantee, so the result is unique.
- `greedy_total` is at most `floor(n / 2) * (n - 1)`, which is below `5 * 10^9` and can exceed `2^31 - 1`; use a 64-bit integer in a fixed-width language.
Constraints
- 1 <= n <= 10^5
- Every A[i] is 0, 1 or 2.
- At every step of the greedy process, exactly one unassigned (person, cake) pair has the smallest distance. Every test input satisfies this guarantee, so the result is unique.
- greedy_total is at most floor(n / 2) * (n - 1), which is below 5 * 10^9 and can exceed 2^31 - 1; use a 64-bit integer in a fixed-width language (long in Java, long long in C++).
Examples
Input: ([1, 0, 2, 0, 0, 1, 2, 0, 1],)
Expected Output: [1, 3]
Explanation: Example 1: closest pair person 5 / cake 6 at distance 1, then person 0 / cake 2 at distance 2; the person at 8 gets no cake.
Input: ([2, 0, 1, 2, 0, 0, 1],)
Expected Output: [1, 7]
Explanation: Example 2: greedy takes person 2 / cake 3 (1), then person 6 / cake 0 (6) for 7; a min-cost matching or a sorted zip of positions would give 5.
Hints
- The first pair the greedy process makes is the closest person-cake pair overall, so its distance also answers the first question.
- Already assigned people and cakes never block a later pair: the distance between a person and a cake depends only on their positions.
- Apply the closest-pair rule literally even when another assignment would cost less, as in Example 2; with unequal counts the extras simply stay unassigned.