Every MEX Reachable With At Most One Bounded Increment

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

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

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

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

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.

Reachable MEX Values After At Most One Block Increment

Hints

1. Blocks that hold the same value are interchangeable: increasing any one of them produces the same multiset of values.
2. 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.
3. The original MEX is always part of the answer, and a block holding n - 1 can never be chosen.

Approach

Count how many blocks hold each value (an array of size n + 1, whose last slot is always 0) and let m be the MEX of the original array; m is always reachable because doing nothing is allowed. Choosing a block with value v (only allowed when v < n - 1) removes one copy of v and adds one copy of v + 1, and every block holding v yields the same multiset, so only distinct values matter. Case 1, v appears at least twice: v stays present, values below v + 1 are unchanged, so the MEX changes only when v + 1 == m. Then m becomes present and the new MEX is the smallest value greater than m that was missing originally (it can be n, which is never present). This applies exactly when m >= 1, m < n and m - 1 appears at least twice. Case 2, v appears exactly once: v disappears. If v < m, every smaller value is still present, so the new MEX is v (even when v + 1 == m). If v > m, m is still missing and nothing below m changed, so the MEX stays m. v == m is impossible because m is absent. Hence the answer is every v < m with count exactly 1 and v < n - 1, then m, then the gap-filling value when the duplicate condition holds; this list is already strictly increasing and duplicate-free. Edge cases: n = 1 allows no operation (the only value is n - 1 = 0), so the answer is [1]; an array without 0 has MEX 0 and increases can never create a 0; in a permutation of 0..n-1 the top value n - 1 cannot be chosen, so the answer is 0..n-2 followed by n.

• Time complexity: O(n)
• Space complexity: O(n)