Katkat
Back

Every MEX Reachable With At Most One Bounded Increment

CitadelSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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 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.