Every MEX Reachable With At Most One Bounded Increment
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
A system has `n` memory blocks. Block `i` holds an integer value `memory_blocks[i]`, and every value satisfies `0 <= memory_blocks[i] < n`. You may perform at most one operation: choose one block whose value is less than `n - 1` and increase its value by 1.
The MEX (minimum excluded value) of the array is the smallest non-negative integer that does not appear in it. Return every MEX value the array can have after performing either no operation or exactly one operation.
### Function Signature
```python
def reachable_mex_values(memory_blocks: list[int]) -> list[int]:
```
### Rules
- An operation picks one index `i` with `memory_blocks[i] < n - 1` and replaces `memory_blocks[i]` with `memory_blocks[i] + 1`. A block whose value is `n - 1` cannot be chosen.
- At most one operation is performed in total. Performing no operation is always allowed, so the MEX of the original array is always reachable.
- Each possible choice of block is evaluated on the original array; choices do not accumulate.
- Return the distinct reachable MEX values in strictly increasing order.
### Constraints
- `1 <= n == len(memory_blocks) <= 10^5`
- `0 <= memory_blocks[i] <= n - 1`
- Values may repeat.
### Examples
**Example 1**
```text
Input: memory_blocks = [0, 1, 2]
Output: [0, 1, 3]
```
With no operation the MEX is 3. Increasing the 0 gives `[1, 1, 2]` with MEX 0, and increasing the 1 gives `[0, 2, 2]` with MEX 1. The 2 equals `n - 1` and cannot be increased, so a MEX of 2 is not reachable.
**Example 2**
```text
Input: memory_blocks = [0, 0, 3, 1, 1]
Output: [2, 4]
```
With no operation the MEX is 2. Increasing a 0 gives `[1, 0, 3, 1, 1]`, whose MEX is still 2. Increasing a 1 gives `[0, 0, 3, 2, 1]`, which contains 0 through 3, so its MEX is 4. Increasing the 3 gives `[0, 0, 4, 1, 1]` with MEX 2.
**Example 3**
```text
Input: memory_blocks = [1, 0, 2, 0]
Output: [1, 2, 3]
```
With no operation the MEX is 3. Increasing a 0 leaves the other 0 in place, so the MEX stays 3. Increasing the 1 gives `[2, 0, 2, 0]` with MEX 1, and increasing the 2 gives `[1, 0, 3, 0]` with MEX 2.
Overview: A coding problem about memory blocks with values below n: using at most one increment of a single value, never raising a value to n, list every minimum excluded value (MEX) the array can end up with. It tests careful case analysis of how one increment can open or fill a gap, handling duplicate values, and returning the sorted answer efficiently.
A system has `n` memory blocks. Block `i` holds the integer `memory_blocks[i]`, and every value satisfies `0 <= memory_blocks[i] <= n - 1`. You may perform at most one operation: choose one block whose value is less than `n - 1` and increase its value by 1.
The MEX (minimum excluded value) of an array is the smallest non-negative integer that does not appear in it. Return every MEX value the array can have after performing either no operation or exactly one operation.
Implement `reachable_mex_values(memory_blocks)`.
### Rules
- An operation picks one index `i` with `memory_blocks[i] < n - 1` and replaces `memory_blocks[i]` with `memory_blocks[i] + 1`. A block whose value is `n - 1` cannot be chosen.
- At most one operation is performed in total. Performing no operation is always allowed, so the MEX of the original array is always reachable.
- Each possible choice of block is evaluated on the original array; choices do not accumulate.
- Return the distinct reachable MEX values as a list in strictly increasing order.
### Constraints
- `1 <= n == len(memory_blocks) <= 10^5`
- `0 <= memory_blocks[i] <= n - 1`
- Values may repeat.
- Every reachable MEX lies in `0..n`, so all input and output values fit in a 32-bit signed integer (none exceeds 2^31 - 1).
### Examples
**Example 1**
```text
Input: memory_blocks = [0, 1, 2]
Output: [0, 1, 3]
```
With no operation the MEX is 3. Increasing the 0 gives `[1, 1, 2]` with MEX 0, and increasing the 1 gives `[0, 2, 2]` with MEX 1. The 2 equals `n - 1` and cannot be increased, so a MEX of 2 is not reachable.
**Example 2**
```text
Input: memory_blocks = [0, 0, 3, 1, 1]
Output: [2, 4]
```
With no operation the MEX is 2. Increasing a 0 gives `[1, 0, 3, 1, 1]`, whose MEX is still 2. Increasing a 1 gives `[0, 0, 3, 2, 1]`, which contains 0 through 3, so its MEX is 4. Increasing the 3 gives `[0, 0, 4, 1, 1]` with MEX 2.
Constraints
- 1 <= n == len(memory_blocks) <= 10^5
- 0 <= memory_blocks[i] <= n - 1
- Values may repeat.
- Every reachable MEX lies in 0..n, so all input and output values fit in a 32-bit signed integer.
Examples
Input: ([0, 1, 2],)
Expected Output: [0, 1, 3]
Explanation: Source Example 1: no operation gives 3, increasing the 0 gives 0, increasing the 1 gives 1; the 2 equals n - 1 and cannot be chosen, so 2 is unreachable.
Input: ([0, 0, 3, 1, 1],)
Expected Output: [2, 4]
Explanation: Source Example 2: increasing a duplicated 1 fills the gap at 2 and the MEX jumps to 4; every other choice keeps MEX 2.
Hints
- Blocks that hold the same value are interchangeable: increasing any one of them produces the same multiset of values.
- A single increment removes one copy of a value and adds one copy of the next value. Consider separately how losing a value and gaining a value can move the smallest missing number.
- The original MEX is always part of the answer, and a block holding n - 1 can never be chosen.