ARRAYS & HASHING · ADVANCED

Coordinate compression

Replace big or spread-out values with their rank among the distinct values, so they can be used as small array indexes.

Time O(n log n)Space O(n)6 practice problemsStep-through picture

The idea

Some algorithms need values to be small array indexes: counting arrays, difference arrays, Fenwick trees. But real data might hold timestamps in the billions, or a few values spread far apart, like [3, 1000000000, 42]. An array that big is impossible.

Often only the order of the values matters, not their size. Coordinate compression keeps the order and throws away the size: sort the distinct values, then replace each value with its position in that sorted list, called its rank. [3, 1000000000, 42] becomes [0, 2, 1].

Now the values fit in an array of length equal to the number of distinct values, and comparisons like "is a less than b" give the same answers as before.

An everyday example

Finishing places in a race

Runners finish a race with times like 3:58.21, 4:02.90, and 3:59.04. For handing out medals, the exact times don't matter, only the order: 1st, 2nd, 3rd. The places are small numbers that keep exactly the same order as the times. Two runners with the same time share a place.

How the example maps to the code
In the example	In the code
The finish times	`values`
The list of distinct times, fastest first	`sorted`
A runner's place	`rankOf.get(value)`
Runners who tied share a place	Equal values map to the same rank

From the slow way to coordinate compression

The obvious way to use values as array indexes is to make an array as long as the largest value. For values up to 9,000 that's fine. For timestamps near 1.7 billion it's impossible, and negative values can't be indexes at all.
Many algorithms only ask questions like "is a less than b?" or "are they equal?". For them, the gap between values doesn't matter. Any replacement that keeps the order and the equalities gives the same answers.
The smallest such replacement is the rank: a value's position among the distinct values in sorted order. With d distinct values, ranks run from 0 to d - 1, so they fit an array of length d. To find ranks, sort the distinct values once.
Finding a value in the sorted list each time would mean a scan, so store a map from value to rank instead. Remove duplicates, sort, number the values, then look each one up: that loop is coordinate compression.

How it works

Collect the distinct values with a Set and sort them ascending into sorted.
Create a Map called rankOf.
For each index i of sorted, store rankOf.set(sorted[i], i).
Replace every value with rankOf.get(value).
Now ranks run from 0 to sorted.length - 1, and a < b exactly when rank(a) < rank(b).

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function compress(values) {
const sorted = [...new Set(values)].sort((a, b) => a - b);
const rankOf = new Map();
for (let i = 0; i < sorted.length; i++) {
rankOf.set(sorted[i], i);
}
return values.map((value) => rankOf.get(value));
}

How fast it is

Time	`O(n log n)`
Extra memory	`O(n)`

Sorting the distinct values is the slowest part. The set, the sorted list, and the map each hold at most n entries.

Best caseO(n)
All values are equal, like [4, 4, 4]: the Set holds one value, sorting it is instant, and the rest is one pass.
Average caseO(n log n)
Sorting the d distinct values costs O(d log d), which is the slowest step when many values are different.
Worst caseO(n log n)
Every value is different, so d = n and the sort works on all n values.

Common mistakes

Calling sort() with no compare function, which sorts numbers as strings: [10, 9, 100] becomes [10, 100, 9].
Not removing duplicates, so equal values get different ranks.
Using sorted.indexOf(value) for each value, which scans the list each time: O(n^2). Use a Map or binary search.
Forgetting that compressed indexes lose distances: neighbors in rank can be far apart in real value.

When to use it

Look for these clues in a problem:

Values are huge (up to 10^9) or negative, but there are only up to about 10^5 of them.
Only the order of values matters, not their exact sizes.
You want to use a counting array, difference array, or Fenwick tree indexed by value.
The problem asks to replace each value by its rank.

Check yourself

Answer each one in your head first, then open it.

What does compress([50, -3, 50]) return?

[1, 0, 1]. The sorted distinct values are [-3, 50].

How long must an array be to be indexed by the trace's ranks?

4, one slot per distinct value, compared with 9,001 to index the original values.

Can you find 9000 - 85 from the ranks 3 and 0?

No. Ranks keep only the order. Read the real values back with sorted[3] and sorted[0].

Why must repeats be removed before giving out ranks?

Otherwise two equal values would sit at two indexes of the sorted list and get different ranks, so equal values would no longer compare as equal.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

#93Rank Values for a Color Scale

medium

#94Compress Point Coordinates

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

sorted holds each distinct value once, in increasing order, so it is strictly increasing. A value's rank is its index there. A smaller value sits at a smaller index, so a < b exactly when rank(a) < rank(b), and a === b exactly when the ranks are equal, because equal values are one entry.

Every value from values went into the Set and so into sorted, which means rankOf.get(value) is never undefined. The ranks are exactly 0 to d - 1 with no gaps, so an array of length d can be indexed by them.

So any algorithm that only compares values, such as counting how many earlier values are smaller, gives the same answer on the ranks. What's lost is size: sums, differences, and lengths of the original values can't be computed from ranks. When you need them, read the real value back with sorted[rank].

Going deeper

3 more ideas

Why order is kept

sorted lists the distinct values from smallest to largest, so a smaller value always sits at a smaller index. Equal values are one entry in sorted, so they get the same rank. That means every comparison between two values gives the same answer when made between their ranks.

Ranks for intervals

For intervals like [start, end] on a huge number line, compress all the starts and ends together. A difference array over the compressed points then works, as long as you remember each compressed index stands for a real coordinate. To measure real lengths, look the real values back up in sorted.

Cost

Sorting the distinct values takes O(n log n) time. Building the map and replacing values takes O(n). The Set, sorted, and rankOf use O(n) space. If you need ranks starting at 1 (common for Fenwick trees), add 1.

Work it by hand

Every step in a table, with why

Compress six spread-out values with repeats into small ranks.

values = [700, 85, 9000, 85, 320, 700]

Step	Step	`i` or `value`	Reads	Result so far	Why
1	Remove repeats	-	6 values	`[700, 85, 9000, 320]`	`new Set(values)` keeps one copy of each value, in first-seen order.
2	Sort	-	4 distinct values	`sorted = [85, 320, 700, 9000]`	The compare function `(a, b) => a - b` sorts by number. Each index in `sorted` will be a rank.
3	Rank	`i = 0`	`sorted[0] = 85`	`85 -> 0`	The smallest value gets rank 0.
4	Rank	`i = 1`	`sorted[1] = 320`	`320 -> 1`	One distinct value is smaller than 320.
5	Rank	`i = 2`	`sorted[2] = 700`	`700 -> 2`	Two distinct values are smaller than 700.
6	Rank	`i = 3`	`sorted[3] = 9000`	`9000 -> 3`	The largest value gets the largest rank, `d - 1 = 3`.
7	Look up	`700`	`rankOf.get(700)`	`[2]`	`values.map` now replaces each value with its rank, in the original order.
8	Look up	`85`	`rankOf.get(85)`	`[2, 0]`	One map lookup per value, no scanning.
9	Look up	`9000`	`rankOf.get(9000)`	`[2, 0, 3]`	9000 becomes 3. The gap of over 8,000 to 700 is gone, but the order is kept.
10	Look up	`85`	`rankOf.get(85)`	`[2, 0, 3, 0]`	The second 85 gets the same rank as the first, because both are one entry in `sorted`.
11	Look up	`320`	`rankOf.get(320)`	`[2, 0, 3, 0, 1]`	320 sits between 85 and 700, and its rank 1 sits between 0 and 2.
12	Look up	`700`	`rankOf.get(700)`	`[2, 0, 3, 0, 1, 2]`	The last value repeats the first, so it gets the same rank.

It returns [2, 0, 3, 0, 1, 2]. The values now fit an array of length 4 instead of 9,001, and every comparison between two values gives the same answer as between their ranks.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Coordinate compression	`O(n log n)`	`O(n)`	Values are huge, negative, or spread out, and the algorithm only needs their order.
Use the values as indexes directly	`O(n + m)`	`O(m)`	Values are non-negative whole numbers up to a small `m`, so no mapping is needed.
Number values in first-seen order	`O(n)`	`O(n)`	Only equality matters, not order, so a `Map` can give out ids 0, 1, 2 without sorting.

Extra memory: O(n): the Set, sorted, rankOf, and the result each hold at most n entries.

How the steps grow

Coordinate compression O(n log n)
Use the values as indexes directly O(n + m)
Number values in first-seen order O(n)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Coordinate compression	33	9,966	20 million
Use the values as indexes directly	20	2,000	2 million
Number values in first-seen order	10	1,000	1 million

Inputs that need care

5 tricky inputs

An empty list: values = []: The Set and sorted are empty, the loop doesn't run, and it returns [].
All equal: values = [4, 4, 4]: There is one distinct value, so every rank is 0: [0, 0, 0].
Negatives: values = [50, -3, 50]: The numeric sort puts -3 first, so it returns [1, 0, 1]. Ranks are never negative, whatever the values.
No compare function: sort() on the trace's values: sort() compares as text, so sorted becomes [320, 700, 85, 9000] and the result is [1, 2, 3, 2, 0, 1], with 85 ranked above 700. Always pass (a, b) => a - b.
Decimals that should match: [0.1 + 0.2, 0.3]: 0.1 + 0.2 is 0.30000000000000004, a different number, so the result is [1, 0]. Round values first if nearly equal numbers should share a rank.

Variations and follow-ups

Twists interviewers add

Binary search instead of a map

Skip rankOf and find each rank with a binary search in sorted. It costs O(log d) per lookup, but it also answers "where would a value that isn't in the list go?", which a map can't.

Counting smaller values with a Fenwick tree

To count, for each value, how many later values are smaller, compress first, then walk from the right and add each rank to a Fenwick tree. Ranks keep the tree's size at d instead of the largest value.

Keeping gaps visible

When painting ranges on a number line, compressing only the endpoints can make two separate ranges look touching. Also add end + 1 for each range to the values, so a rank exists for the first spot after each range.

Dense ranking for leaderboards

Ranking scores so that ties share a rank and the next rank follows without a jump, like 1, 2, 2, 3, is exactly this algorithm, with ranks plus 1 and the sort reversed.

In an interview

Spot it, explain it, answer follow-ups

Spot it from constraints like "values up to 10^9, but at most 10^5 of them", combined with a structure indexed by value, such as a Fenwick tree or a counting array.
Say why it's safe: "the algorithm only compares values, and ranks keep every comparison the same."
Test by hand: repeated values, negative values, and values whose text order differs from their number order.
The usual follow-up is "what if new values arrive later?". Answer: if you know all of them up front, including the ones in queries, compress them all together first. If not, use a sorted structure that can insert, like a balanced tree.

Where frontend code uses it

The same idea in real UI code

Turning timestamps from analytics events into column numbers for a heatmap or timeline chart, where only the order of events matters.
Building a rank-based color scale, where each value gets a color by its rank instead of its size.
Mapping scattered numeric ids to compact indexes, so they can index into typed arrays such as Uint32Array for fast lookups.

Coordinate compression

The idea

An everyday example

Finishing places in a race

From the slow way to coordinate compression

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why order is kept

Ranks for intervals

Cost

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Binary search instead of a map

Counting smaller values with a Fenwick tree

Keeping gaps visible

Dense ranking for leaderboards

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Finishing places in a race

From the slow way to coordinate compression

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why order is kept

Ranks for intervals

Cost

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Binary search instead of a map

Counting smaller values with a Fenwick tree

Keeping gaps visible

Dense ranking for leaderboards

In an interview

Where frontend code uses it

Related algorithms