First Free Locker Number After One Tag Bump

A gym has n lockers, and each locker carries a numbered tag. Tag numbers are integers from 0 to n - 1, and several lockers may share the same number. The front desk always hands a new member the first free number: the smallest non-negative integer that no locker currently carries (also called the MEX).

A staff member is allowed to make at most one adjustment before the next member arrives: pick one locker whose tag is less than n - 1 and add 1 to its tag. Tags can never go above n - 1.

Return every first-free number the desk could end up handing out, sorted in increasing order.

def possible_first_gaps(tags: list[int]) -> list[int]:

Rules

• Making no adjustment is allowed, so the first free number of the original list is always in the answer.
• Each candidate adjustment is applied to the original list on its own. Adjustments never stack.
• Return distinct values in strictly increasing order.

Examples

Example 1

tags   = [0, 2, 1, 2, 4, 0]      (n = 6)
Output = [1, 3, 5]

• No adjustment: 0, 1 and 2 are present and 3 is missing, so the answer is 3.
• Bump the only 1 to 2: now 1 is missing, so the answer is 1.
• Bump one of the two 2s to 3: 0 to 4 are all present and 5 is missing, so the answer is 5.
• Bumping a 0 (there are two) or the 4 leaves the answer at 3.

Example 2

tags   = [0, 1, 2, 3]            (n = 4)
Output = [0, 1, 2, 4]

Bumping 0, 1 or 2 opens a gap at that value. The tag 3 equals n - 1, so it cannot be bumped, and 3 is never reachable.

Constraints

• 1 <= n <= 2 * 10^5
• 0 <= tags[i] <= n - 1
• Aim for O(n) time. Recomputing the MEX for every possible bump (O(n^2)) is too slow.