Coordinate compression: keep the order
Picture
Points lie at 10, 1,000,000, and 30. An array with a million cells wastes space.
Predict
What does coordinate compression preserve?
Walk through the small example
Order and equality. Algorithms need relative order or indexing, not numeric gaps.
Mental model and complete Python solution
Compression removes unused address space, not information your algorithm needs. Before compressing, state whether it needs order, equality, adjacency, or real distances.
What the function promises: Return compressed ranks and the sorted unique values needed to decode them.
def compress(values):
ordered = sorted(set(values))
rank = {value: i for i, value in enumerate(ordered)}
return [rank[value] for value in values], ordered
ranks, keys = compress([10, 1_000_000, 30, 10])
assert ranks == [0,2,1,0]
assert [keys[i] for i in ranks] == [10,1_000_000,30,10]Work and storage: O(n log n) time and O(n) space.
When to recognize it: Algorithms need relative order or indexing, not numeric gaps.
Check before applying it: Using rank differences as original distances changes the problem.
Change one rule
Coordinates arrive online and new values must fit between old ranks.
See what changes
Static ranks may shift; use an ordered tree, dynamic structure, or collect coordinates before processing.
Connect
Sorting: buy useful order: Sorted unique values define stable ranks.
Fenwick tree: prefix sums with updates: Dense ranks let a tree index sparse values.