22.06Intermediate5 topics15 min5 interactive animations

Coordinate compression

Coordinate compression: mapping large values to small ranks, preserving duplicates, inverse mappings and updating compressed intervals.

Learning goals

Replace huge coordinates by dense ranks without changing their order
Handle duplicates with dense versus ordinal ranks
Map ranks back to original values
Apply range updates to compressed coordinates

Prerequisites

Difference array and event sweepBinary search

An algorithm that indexes an array by coordinate cannot handle values up to a billion, yet only the relative order of the values usually matters. Compression keeps the order and throws away the empty space.

22.06.1

Rank mapping

**Coordinate compression** replaces each value with its **rank** among the distinct values, so [100, 5000000, 7, 100, 999999, -20] becomes [2, 4, 1, 2, 3, 0]. The relative order is preserved, so comparisons between values give the same results, and the new values lie in 0..k-1 where k is the number of distinct values.

Algorithm: copy the values, sort, remove duplicates, then rank each original value with binary search. Cost O(n log n). The animation shows the sorted distinct list and each value moving to its rank.

Java

1static int[] compress(int[] values) {
2    int[] sorted = Arrays.stream(values).sorted().distinct().toArray();
3    int[] ranks = new int[values.length];
4    for (int i = 0; i < values.length; i++) {
5        ranks[i] = Arrays.binarySearch(sorted, values[i]);   // position among the distinct values
6    }
7    return ranks;
8}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Coordinate compression: ranks and the inverse mapping

Interactive · edit the input

int[] arr · length 6

100

5000000

100

999999

-20

012345

Value being rankedIts rank slot

sorted distinct values (inverse mapping)

-20rank 0

7rank 1

100rank 2

999999rank 3

5000000rank 4

ranks of the input

?idx 0

?idx 1

?idx 2

?idx 3

?idx 4

?idx 5

Setup

6 values spread over 5000021 possible numbers, but only the relative order matters for many algorithms. Replace each value by its rank (5 distinct ranks 0..4) and use arrays of that small size.

Step 1 / 8

Java

1static int[] denseRank(int[] a) {
2    int[] sorted = Arrays.stream(a).distinct().sorted().toArray();        // sorted[rank] is the inverse mapping
3    int[] rank = new int[a.length];
4    for (int i = 0; i < a.length; i++) rank[i] = Arrays.binarySearch(sorted, a[i]);   // rank = index among the distinct values
5    return rank;
6}
7static int[] ordinalRank(int[] a) {
8    Integer[] idx = new Integer[a.length]; for (int i = 0; i < idx.length; i++) idx[i] = i;
9    Arrays.sort(idx, Comparator.comparingInt(i -> a[i]));                  // stable: equal values keep their input order
10    int[] rank = new int[a.length];
11    for (int r = 0; r < idx.length; r++) rank[idx[r]] = r;                  // the r-th smallest element gets rank r
12    return rank;
13}

Live state

values

distinct

range

-20..5000000

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	values=6 distinct=5 range=-20..5000000	6 values spread over 5000021 possible numbers, but only the relative order matters for many algorithms. Replace each value by its rank (5 distinct ranks 0..4) and use arrays of that small size.
2	L4	value=100 rank=2	100 is at index 2 among the sorted distinct values (binary search): rank 2.
3	L4	value=5000000 rank=4	5000000 is at index 4 among the sorted distinct values (binary search): rank 4.
4	L4	value=7 rank=1	7 is at index 1 among the sorted distinct values (binary search): rank 1.
5	L4	value=100 rank=2	100 is at index 2 among the sorted distinct values (binary search): rank 2. A repeated value reuses its earlier rank.
6	L4	value=999999 rank=3	999999 is at index 3 among the sorted distinct values (binary search): rank 3.
7	L4	value=-20 rank=0	-20 is at index 0 among the sorted distinct values (binary search): rank 0.
8	L5	return=[2, 4, 1, 2, 3, 0]	Ranks [2, 4, 1, 2, 3, 0]. The inverse mapping turns a rank back into the original value in O(1).

22.06.2

Compress large coordinates

When intervals have endpoints up to 10^9 but there are only a few hundred of them, a difference array over the coordinate range is impossible and compression makes it work: gather every endpoint, sort and deduplicate them, and treat the stretches between consecutive distinct endpoints as **elementary segments**. Coverage is constant on each elementary segment, so one difference array of size (distinct endpoints) answers everything.

The “Big coordinates” preset has intervals 10-500000, 100-9000000 and 400000-800000: the six distinct endpoints give five elementary segments, and the coverage per segment is [1, 2, 3, 2, 1] with maximum overlap 3. The work depends on n only, not on how large the coordinates are.

Java

1// half-open intervals with huge endpoints; returns the maximum number overlapping at any point
2static int maxOverlapCompressed(int[][] intervals) {
3    int[] xs = Arrays.stream(intervals).flatMapToInt(iv -> IntStream.of(iv[0], iv[1])).sorted().distinct().toArray();
4    int[] diff = new int[xs.length + 1];
5    for (int[] iv : intervals) {
6        diff[Arrays.binarySearch(xs, iv[0])]++;
7        diff[Arrays.binarySearch(xs, iv[1])]--;
8    }
9    int running = 0, best = 0;
10    for (int i = 0; i < xs.length; i++) { running += diff[i]; best = Math.max(best, running); }
11    return best;
12}

Range updates on huge coordinates through compression

Interactive · edit the input

compressed coordinates

10#0

100#1

400000#2

500000#3

800000#4

9000000#5

difference array

0#0

0#1

0#2

0#3

0#4

0#5

coverage of [x#i, x#i+1)

none

Setup

The ranges span 8999990 units, but only 6 distinct endpoints matter: between two neighbouring endpoints the coverage cannot change. Compress to 6 coordinates and use a difference array of that size.

Step 1 / 10

Java

1static int[] coverage(int[][] ranges) {                          // half-open [l, r); returns the count on each elementary segment
2    int[] xs = Arrays.stream(ranges).flatMapToInt(r -> IntStream.of(r[0], r[1])).distinct().sorted().toArray();   // compress
3    int[] diff = new int[xs.length + 1];
4    for (int[] r : ranges) {
5        diff[Arrays.binarySearch(xs, r[0])]++;                       // +1 at the compressed start
6        diff[Arrays.binarySearch(xs, r[1])]--;                       // -1 at the compressed end
7    }
8    int[] cover = new int[xs.length - 1]; int run = 0;
9    for (int i = 0; i < cover.length; i++) { run += diff[i]; cover[i] = run; }      // prefix sums give coverage of [xs[i], xs[i+1])
10    return cover;
11}

Live state

ranges

endpoints

span

10..9000000

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	ranges=3 endpoints=6 span=10..9000000	The ranges span 8999990 units, but only 6 distinct endpoints matter: between two neighbouring endpoints the coverage cannot change. Compress to 6 coordinates and use a difference array of that size.
2	L5	range=10-500000 +1 at=#0 −1 at=#3	Range [10, 500000): add +1 at compressed index 0 and −1 at index 3.
3	L5	range=100-9000000 +1 at=#1 −1 at=#5	Range [100, 9000000): add +1 at compressed index 1 and −1 at index 5.
4	L5	range=400000-800000 +1 at=#2 −1 at=#4	Range [400000, 800000): add +1 at compressed index 2 and −1 at index 4.
5	L9	index=0 running=1	Running sum 1: one range covers [10, 100).
6	L9	index=1 running=2	Running sum 2: 2 ranges cover [100, 400000).
7	L9	index=2 running=3	Running sum 3: 3 ranges cover [400000, 500000).
8	L9	index=3 running=2	Running sum 2: 2 ranges cover [500000, 800000).
9	L9	index=4 running=1	Running sum 1: one range covers [800000, 9000000).
10	L10	return=[1, 2, 3, 2, 1] max=3	Coverage per elementary segment: [1, 2, 3, 2, 1]. The maximum overlap is 3. Work: O(n log n), independent of the coordinate magnitudes.

22.06.3

Duplicate preservation

Two ways to rank values with duplicates. **Dense rank** gives equal values the same rank and leaves no gaps: [100, 5000000, 7, 100, 999999, -20] becomes [2, 4, 1, 2, 3, 0], the first preset. **Ordinal rank** (position in the sorted order) breaks ties by original position so every element gets a unique rank: the second preset gives [2, 5, 1, 3, 4, 0], where the two 100s receive ranks 2 and 3.

Dense ranks are right when equal values must stay equal (counting distinct values, comparing). Ordinal ranks are right when you need a permutation of 0..n-1, for example when a Fenwick tree needs a distinct slot per element to count inversions.

Java

1// ordinal ranks: a permutation of 0..n-1, ties broken by original index (stable)
2static int[] ordinalRanks(int[] values) {
3    Integer[] idx = new Integer[values.length];
4    for (int i = 0; i < idx.length; i++) idx[i] = i;
5    Arrays.sort(idx, Comparator.comparingInt(i -> values[i]));   // stable: equal values keep input order
6    int[] rank = new int[values.length];
7    for (int r = 0; r < idx.length; r++) rank[idx[r]] = r;
8    return rank;
9}

Coordinate compression: ranks and the inverse mapping

Interactive · edit the input

int[] arr · length 6

100

5000000

100

999999

-20

012345

Value being rankedIts rank slot

sorted distinct values (inverse mapping)

-20rank 0

7rank 1

100rank 2

999999rank 3

5000000rank 4

ranks of the input

?idx 0

?idx 1

?idx 2

?idx 3

?idx 4

?idx 5

Setup

6 values spread over 5000021 possible numbers, but only the relative order matters for many algorithms. Replace each value by its rank (5 distinct ranks 0..4) and use arrays of that small size.

Step 1 / 8

Java

1static int[] denseRank(int[] a) {
2    int[] sorted = Arrays.stream(a).distinct().sorted().toArray();        // sorted[rank] is the inverse mapping
3    int[] rank = new int[a.length];
4    for (int i = 0; i < a.length; i++) rank[i] = Arrays.binarySearch(sorted, a[i]);   // rank = index among the distinct values
5    return rank;
6}
7static int[] ordinalRank(int[] a) {
8    Integer[] idx = new Integer[a.length]; for (int i = 0; i < idx.length; i++) idx[i] = i;
9    Arrays.sort(idx, Comparator.comparingInt(i -> a[i]));                  // stable: equal values keep their input order
10    int[] rank = new int[a.length];
11    for (int r = 0; r < idx.length; r++) rank[idx[r]] = r;                  // the r-th smallest element gets rank r
12    return rank;
13}

Live state

values

distinct

range

-20..5000000

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	values=6 distinct=5 range=-20..5000000	6 values spread over 5000021 possible numbers, but only the relative order matters for many algorithms. Replace each value by its rank (5 distinct ranks 0..4) and use arrays of that small size.
2	L4	value=100 rank=2	100 is at index 2 among the sorted distinct values (binary search): rank 2.
3	L4	value=5000000 rank=4	5000000 is at index 4 among the sorted distinct values (binary search): rank 4.
4	L4	value=7 rank=1	7 is at index 1 among the sorted distinct values (binary search): rank 1.
5	L4	value=100 rank=2	100 is at index 2 among the sorted distinct values (binary search): rank 2. A repeated value reuses its earlier rank.
6	L4	value=999999 rank=3	999999 is at index 3 among the sorted distinct values (binary search): rank 3.
7	L4	value=-20 rank=0	-20 is at index 0 among the sorted distinct values (binary search): rank 0.
8	L5	return=[2, 4, 1, 2, 3, 0]	Ranks [2, 4, 1, 2, 3, 0]. The inverse mapping turns a rank back into the original value in O(1).

22.06.4

Inverse mapping

After computing on ranks, results often have to be reported in the original units. The **inverse mapping** is just the sorted distinct array: original = sorted[rank], which is O(1). Keep it for as long as you need to translate, and remember that for ordinal ranks you also need the original index list to recover the value of each element.

The animation ends by showing that the inverse mapping turns a rank back into the original value in O(1). A typical use: compress the endpoints, find the best interval in rank space, then output sorted[rank] as the real coordinate.

Java

1// returns the original value of each rank, then translates a result back
2static int[] distinctSorted(int[] values) {
3    return Arrays.stream(values).sorted().distinct().toArray();
4}
5
6static int original(int[] distinctSorted, int rank) {
7    return distinctSorted[rank];                             // inverse of Arrays.binarySearch(distinctSorted, value)
8}

Coordinate compression: ranks and the inverse mapping

Interactive · edit the input

int[] arr · length 6

100

5000000

100

999999

-20

012345

Value being rankedIts rank slot

sorted distinct values (inverse mapping)

-20rank 0

7rank 1

100rank 2

999999rank 3

5000000rank 4

ranks of the input

?idx 0

?idx 1

?idx 2

?idx 3

?idx 4

?idx 5

Setup

6 values spread over 5000021 possible numbers, but only the relative order matters for many algorithms. Replace each value by its rank (5 distinct ranks 0..4) and use arrays of that small size.

Step 1 / 8

Java

1static int[] denseRank(int[] a) {
2    int[] sorted = Arrays.stream(a).distinct().sorted().toArray();        // sorted[rank] is the inverse mapping
3    int[] rank = new int[a.length];
4    for (int i = 0; i < a.length; i++) rank[i] = Arrays.binarySearch(sorted, a[i]);   // rank = index among the distinct values
5    return rank;
6}
7static int[] ordinalRank(int[] a) {
8    Integer[] idx = new Integer[a.length]; for (int i = 0; i < idx.length; i++) idx[i] = i;
9    Arrays.sort(idx, Comparator.comparingInt(i -> a[i]));                  // stable: equal values keep their input order
10    int[] rank = new int[a.length];
11    for (int r = 0; r < idx.length; r++) rank[idx[r]] = r;                  // the r-th smallest element gets rank r
12    return rank;
13}

Live state

values

distinct

range

-20..5000000

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	values=6 distinct=5 range=-20..5000000	6 values spread over 5000021 possible numbers, but only the relative order matters for many algorithms. Replace each value by its rank (5 distinct ranks 0..4) and use arrays of that small size.
2	L4	value=100 rank=2	100 is at index 2 among the sorted distinct values (binary search): rank 2.
3	L4	value=5000000 rank=4	5000000 is at index 4 among the sorted distinct values (binary search): rank 4.
4	L4	value=7 rank=1	7 is at index 1 among the sorted distinct values (binary search): rank 1.
5	L4	value=100 rank=2	100 is at index 2 among the sorted distinct values (binary search): rank 2. A repeated value reuses its earlier rank.
6	L4	value=999999 rank=3	999999 is at index 3 among the sorted distinct values (binary search): rank 3.
7	L4	value=-20 rank=0	-20 is at index 0 among the sorted distinct values (binary search): rank 0.
8	L5	return=[2, 4, 1, 2, 3, 0]	Ranks [2, 4, 1, 2, 3, 0]. The inverse mapping turns a rank back into the original value in O(1).

22.06.5

Compressed interval updates

Combining the ideas: compress the endpoints of half-open intervals, add 1 to the compressed start and subtract 1 at the compressed end in a difference array, and a prefix sum yields the coverage of every **elementary segment**. Coverage of the original range between two endpoints is the coverage of its elementary segment.

The “Shared endpoints” preset (1-5, 5-9, 1-9) has two elementary segments [1,5) and [5,9) with coverage [2, 2] and maximum 2: the intervals 1-5 and 5-9 do not overlap each other because they are half-open. “Disjoint” (0-1000000 and 2000000-3000000) has coverage [1, 0, 1], showing the empty gap, and “Identical ranges” collapses into one segment with coverage 3.

Java

1// coverage of each elementary segment between consecutive distinct endpoints
2static int[] segmentCoverage(int[][] intervals) {
3    int[] xs = Arrays.stream(intervals).flatMapToInt(iv -> IntStream.of(iv[0], iv[1])).sorted().distinct().toArray();
4    int[] diff = new int[xs.length];
5    for (int[] iv : intervals) {
6        diff[Arrays.binarySearch(xs, iv[0])]++;
7        diff[Arrays.binarySearch(xs, iv[1])]--;
8    }
9    int[] cover = new int[xs.length - 1];
10    int running = 0;
11    for (int i = 0; i + 1 < xs.length; i++) { running += diff[i]; cover[i] = running; }
12    return cover;                                            // cover[i] applies to [xs[i], xs[i + 1])
13}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Range updates on huge coordinates through compression

Interactive · edit the input

compressed coordinates

10#0

100#1

400000#2

500000#3

800000#4

9000000#5

difference array

0#0

0#1

0#2

0#3

0#4

0#5

coverage of [x#i, x#i+1)

none

Setup

The ranges span 8999990 units, but only 6 distinct endpoints matter: between two neighbouring endpoints the coverage cannot change. Compress to 6 coordinates and use a difference array of that size.

Step 1 / 10

Java

1static int[] coverage(int[][] ranges) {                          // half-open [l, r); returns the count on each elementary segment
2    int[] xs = Arrays.stream(ranges).flatMapToInt(r -> IntStream.of(r[0], r[1])).distinct().sorted().toArray();   // compress
3    int[] diff = new int[xs.length + 1];
4    for (int[] r : ranges) {
5        diff[Arrays.binarySearch(xs, r[0])]++;                       // +1 at the compressed start
6        diff[Arrays.binarySearch(xs, r[1])]--;                       // -1 at the compressed end
7    }
8    int[] cover = new int[xs.length - 1]; int run = 0;
9    for (int i = 0; i < cover.length; i++) { run += diff[i]; cover[i] = run; }      // prefix sums give coverage of [xs[i], xs[i+1])
10    return cover;
11}

Live state

ranges

endpoints

span

10..9000000

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	ranges=3 endpoints=6 span=10..9000000	The ranges span 8999990 units, but only 6 distinct endpoints matter: between two neighbouring endpoints the coverage cannot change. Compress to 6 coordinates and use a difference array of that size.
2	L5	range=10-500000 +1 at=#0 −1 at=#3	Range [10, 500000): add +1 at compressed index 0 and −1 at index 3.
3	L5	range=100-9000000 +1 at=#1 −1 at=#5	Range [100, 9000000): add +1 at compressed index 1 and −1 at index 5.
4	L5	range=400000-800000 +1 at=#2 −1 at=#4	Range [400000, 800000): add +1 at compressed index 2 and −1 at index 4.
5	L9	index=0 running=1	Running sum 1: one range covers [10, 100).
6	L9	index=1 running=2	Running sum 2: 2 ranges cover [100, 400000).
7	L9	index=2 running=3	Running sum 3: 3 ranges cover [400000, 500000).
8	L9	index=3 running=2	Running sum 2: 2 ranges cover [500000, 800000).
9	L9	index=4 running=1	Running sum 1: one range covers [800000, 9000000).
10	L10	return=[1, 2, 3, 2, 1] max=3	Coverage per elementary segment: [1, 2, 3, 2, 1]. The maximum overlap is 3. Work: O(n log n), independent of the coordinate magnitudes.

Practice ladder

Now try it yourself

Easy

Rank Transform of an Array
Relative Ranks

Medium

Count of Smaller Numbers After Self
My Calendar III
Rank Transform of a Matrix

Advanced

Falling Squares
Count of Range Sum

Key takeaways

Compression keeps the order of values and replaces them by ranks 0..k-1.
Dense ranks keep equal values equal; ordinal ranks make every element unique.
The sorted distinct array is the inverse mapping, and rank-to-value lookup is O(1).
Elementary segments between consecutive endpoints have constant coverage, so a difference array over them answers range updates in O(n log n).