Sign in to watch this lesson
Advanced - Arrays, Sorting and Searching Ā· 4:48
Coordinate Compression and MEX
Coordinate compression turns values as large as 10^18 into array indices without losing their order: sort, unique plus erase, then lower_bound. The MEX, the smallest missing non-negative integer, never exceeds n, so n + 1 flags compute it once and a set of missing numbers keeps it under updates. We also measure why clearing only what you touched beats a memset per test.
You will learn
- Compress values with sort, unique + erase and lower_bound in O(n log n), keeping their order
- Avoid the classic traps: the missing erase, and query values that were not compressed (go offline)
- Compute the MEX in O(n) using MEX <= n, ignoring values above n
- Maintain the MEX under updates with value counts and an ordered set of missing numbers in [0, n]