MEX (Minimum Excludant)
Bucket-array algorithm | scan | hash-set | sort | step-by-step visualization
Input array
Load
Random
Empty
Full [0..n-1]
Input cells (values; index shown above)
Algorithm
Bucket array O(n)
Hash set O(n) avg
Sort + scan O(n log n)
Compare all three
Slow
Fast
Run
Step
Pause
Reset
Operation Log
State
Input size n
0
Bucket size
0
Marked values
0
Scan pointer
-
MEX result
-
Step
0
Last Operation
Load an input and press
Run
or
Step
.
Big-O
Bucket array:
O(n)
time,
O(n)
space
Hash set scan:
O(n)
avg,
O(n)
space
Sort + scan:
O(n log n)
time,
O(1)
extra
Invariant:
MEX ≤ n always.
Legend
Empty bucket
Marked (present)
Currently marking
Scan pointer
MEX found
Out of range (> n)