SyntaxPilot
Courses/Competitive Programming/Lesson 9

Competitive Programming · Lesson 9 of 90 · 11 min

Coordinate compression

queued

These are the notes for Competitive Programming episode 9. Episodes 7 and 8 gave every position its own array cell. Here positions go up to 10^9, so that rule breaks: an array would need about 3.7 GB, and walking every position gets Time Limit Exceeded. The fix keeps only the order of the few numbers that appear (like runners lined up by bib number): sort, unique + erase, lower_bound. That is coordinate compression. Then we run episode 7's difference array on the compressed points, with real piece lengths, and see two bugs with their real outputs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The problem: Festival Road

Problem I · Festival Road (written for this course). A road has positions 1 .. 10^9. There are n lamp strings; string i lights every integer position from l to r (both included). Print two numbers: the largest number of strings on one position, and how many positions are lit by at least one string.

1 ≤ n ≤ 2·10^5, 1 ≤ l ≤ r ≤ 10^9.

Sample input Sample output
4
3 7
5 12
1000000 1000003
6 6
3 14

Position 6 is under three strings ([3,7], [5,12], [6,6]). The lit positions are 3..12 (10 positions) and 1000000..1000003 (4 positions): 14.

Why the old tricks fail

An array per position. Episode 7's difference array needs a cell for every position. How big is that?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll cells = 1000000001;          // positions 0 .. 10^9
    ll bytes = cells * sizeof(int);
    cout << bytes / (1024 * 1024) << " MB\n";
    return 0;
}

Output:

3814 MB

Almost 4 GB against a typical 256 MB limit: Memory Limit Exceeded.

A map, walking every position. A map (a sorted key → value table that only stores keys you insert) avoids the giant array:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    map<int, int> lamps;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        for (int x = l; x <= r; x++) lamps[x]++;
    }
    int best = 0;
    for (auto [x, c] : lamps) best = max(best, c);
    cout << best << ' ' << lamps.size() << '\n';
    return 0;
}

It prints 3 14 on the sample. On three long strings (1 1000000000, 2 999999999, 500000000 500000000) it walks about 2·10^9 positions and gets Time Limit Exceeded in the SyntaxPilot compiler. The cost grows with the length of the road, not with n.

The observation. There are only 2n endpoints (at most 4·10^5 numbers), and between two neighbouring endpoints nothing changes. Only those numbers, and their order, matter.

The idea: bib numbers on sports day

On sports day In code
Bibs 7, 42, 100, 1000000000: huge numbers, few runners values up to 10^9, only a few of them
Line the runners up by bib number sort
The same bib twice is the same runner unique + erase
Each runner gets a lane 0, 1, 2, 3 by his place in the line lower_bound gives each value its index

Coordinate compression

Coordinate compression replaces each value by its index among the sorted distinct values. The order is kept: a < b exactly when id(a) < id(b).

vector<int> xs = a;                                   // copy the values
sort(xs.begin(), xs.end());                           // 1. sort
xs.erase(unique(xs.begin(), xs.end()), xs.end());     // 2. drop repeats
int id = lower_bound(xs.begin(), xs.end(), v) - xs.begin();   // 3. index of v
  • unique moves consecutive repeats to the end and returns an iterator to where the clean part stops; it does not shrink the vector. erase cuts off the rest.
  • lower_bound is a built-in binary search: it returns an iterator (a pointer-like position) to the first element that is not less than v. Subtracting xs.begin() turns it into an index.
  • Cost: sorting O(n log n), each lookup O(log n).

The six values from the video:

a 100 7 1000000000 7 42 100
sorted 7 7 42 100 100 1000000000
unique xs 7 42 100 1000000000
index 2 0 3 0 1 2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    vector<int> xs = a;
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for (int i = 0; i < n; i++) {
        int id = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
        cout << id << " \n"[i == n - 1];
    }
    return 0;
}

Input 6 / 100 7 1000000000 7 42 100, output:

2 0 3 0 1 2

The missing-unique bug (real output)

Delete the xs.erase(unique(...), xs.end()); line and run the same input:

3 0 5 0 2 3

The order is still right, but indices skip: the largest is 5 with only 4 distinct values. Any array sized by the number of distinct values now goes out of bounds, and equal values that should be next to each other get gaps between them.

Back to the road: compress l and r + 1

A string switches on at l and off at r + 1. Those are the only places the answer can change, so compress all l and r + 1 values (at most 2n points) and run the difference array on the points: +1 at id(l), −1 at id(r + 1). Between point k and point k + 1, the lamps don't change, and that piece of road is xs[k+1] − xs[k] positions long.

The sample:

k 0 1 2 3 4 5 6 7
xs[k] 3 5 6 7 8 13 1000000 1000004
lamps on piece k 1 2 3 2 1 0 1
piece length 2 1 1 1 5 999987 4

Maximum 3; lit = 2 + 1 + 1 + 1 + 5 + 4 = 14.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> l(n), r(n), xs;
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
        xs.push_back(l[i]);
        xs.push_back(r[i] + 1);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    auto id = [&](int v) { return lower_bound(xs.begin(), xs.end(), v) - xs.begin(); };
    vector<int> d(xs.size() + 1, 0);
    for (int i = 0; i < n; i++) {
        d[id(l[i])]++;
        d[id(r[i] + 1)]--;
    }
    int cur = 0, best = 0;
    ll lit = 0;
    for (int k = 0; k + 1 < (int)xs.size(); k++) {
        cur += d[k];
        best = max(best, cur);
        if (cur > 0) lit += xs[k + 1] - xs[k];
    }
    cout << best << ' ' << lit << '\n';
    return 0;
}
Input Output
the sample 3 14
3 / 1 1000000000 / 2 999999999 / 500000000 500000000 3 1000000000 (instantly)

The r vs r + 1 bug (real output)

Compressing r instead of r + 1 (and subtracting at id(r) + 1) prints, on the sample:

3 1000000

The maximum is still right, but the length is wrong. The string [5, 12] should switch off at 13, but 13 was never recorded as a point; the next recorded point after 12 is 1000000, so the light "stays on" across the whole dark gap. Rule: every position where the answer changes must be a point. A stress test against the map brute force on small positions (episode 5) catches this immediately.

Solutions in C++, Java and Python

C++: the Festival Road program above.

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken(); int n = (int) st.nval;
        int[] l = new int[n], r = new int[n];
        int[] xs = new int[2 * n];
        for (int i = 0; i < n; i++) {
            st.nextToken(); l[i] = (int) st.nval;
            st.nextToken(); r[i] = (int) st.nval;
            xs[2 * i] = l[i];
            xs[2 * i + 1] = r[i] + 1;
        }
        Arrays.sort(xs);
        int m = 0;
        for (int i = 0; i < xs.length; i++) if (i == 0 || xs[i] != xs[i - 1]) xs[m++] = xs[i];
        int[] d = new int[m + 1];
        for (int i = 0; i < n; i++) {
            d[Arrays.binarySearch(xs, 0, m, l[i])]++;
            d[Arrays.binarySearch(xs, 0, m, r[i] + 1)]--;
        }
        int cur = 0, best = 0;
        long lit = 0;
        for (int k = 0; k + 1 < m; k++) {
            cur += d[k];
            best = Math.max(best, cur);
            if (cur > 0) lit += xs[k + 1] - xs[k];
        }
        System.out.println(best + " " + lit);
    }
}

Python

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    l = list(map(int, data[1:2 * n + 1:2]))
    r = list(map(int, data[2:2 * n + 2:2]))
    xs = sorted(set(l + [x + 1 for x in r]))
    d = [0] * (len(xs) + 1)
    for a, b in zip(l, r):
        d[bisect_left(xs, a)] += 1
        d[bisect_left(xs, b + 1)] -= 1
    cur = best = lit = 0
    for k in range(len(xs) - 1):
        cur += d[k]
        best = max(best, cur)
        if cur > 0:
            lit += xs[k + 1] - xs[k]
    print(best, lit)

main()

All three print 3 14 on the sample (Python and Java tested with the same input).

Brute force vs optimal

Map per position Array of 10^9 Compressed
Time O(total length · log) up to 2·10^14 O(10^9) O(n log n)
Memory grows with the length 3.7 GB O(n)
Verdict at the limits TLE MLE instant

Common mistakes (and the real messages)

Mistake What you see Why Fix
sort without unique + erase 3 0 5 0 2 3 instead of 2 0 3 0 1 2 repeats keep their own slots xs.erase(unique(xs.begin(), xs.end()), xs.end())
Compressing r instead of r + 1 3 1000000 instead of 3 14 the switch-off point is missing push l and r + 1
unique without erase junk values left at the end of xs unique doesn't change the size erase from its return value
lit as int overflow on long roads lengths add up past 2.1·10^9 in harder versions long long
vector<int> d(1000000001) Memory Limit Exceeded 3814 MB compress first
Looking up a value that was never inserted wrong index (lower_bound returns the next bigger one) r was compressed, then r + 1 was looked up look up only values you pushed

Mini project: dense ranks

Give every student's score a rank starting from 1, where equal scores share a rank and there are no gaps (a dense rank). It is compression plus one:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    vector<int> xs = a;
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for (int i = 0; i < n; i++)
        cout << lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin() + 1 << " \n"[i == n - 1];
}

Input 4 / 90 75 90 60, output: 3 2 3 1.

Practice

  1. Change Festival Road to print how many positions are covered by at least 2 strings.

    Answer Replace <code>if (cur > 0)</code> with <code>if (cur >= 2)</code>. On the sample it prints <code>3 3</code> (positions 5, 6, 7).

  2. Why do we compress r + 1 and not r?

    Answer The lamps change right after <code>r</code>, at <code>r + 1</code>. Every position where the count changes must be a point, or a piece will wrongly extend to the next recorded point.

  3. What does the rank program print for 5 / 3 3 3 3 3?

    Answer <code>0 0 0 0 0</code>: one distinct value.

  4. Count pairs i < j with a[i] > a[j] (inversions) when values go up to 10^9.

    Answer Compress the values to 0..m−1 so they fit an array, then count with merge sort or a counting structure in O(n log n). Compression is the step that makes the array small enough.

  5. Values are long long up to 10^18. What changes?

    Answer Only the types: <code>vector<long long> xs</code>. Sorting and <code>lower_bound</code> work the same.

Quick quiz

Input 4 / 50 20 50 90. What does the rank program print?

A) 1 0 1 2 · B) 2 0 2 3 · C) 1 0 2 3 · D) 0 1 0 2

Answer

A. xs = [20, 50, 90], so 50 → 1, 20 → 0, 50 → 1, 90 → 2. Without unique it prints 1 0 1 3 (real output).

Interview questions

  1. What is coordinate compression and when do you need it? Mapping values to their rank among the sorted distinct values. Needed when values are huge (10^9) but few (2·10^5), and you want arrays indexed by value.
  2. Why erase(unique(...)) and not just unique? unique only moves repeats to the end and returns the new logical end; erase removes them.
  3. How do you get a value's compressed index? lower_bound(xs.begin(), xs.end(), v) - xs.begin(), O(log n).
  4. Union length of many intervals with coordinates up to 10^9? Compress the endpoints (l and r + 1 for closed integer intervals), sweep with a running count, and add xs[k+1] − xs[k] for pieces with count > 0.
  5. Does compression change the answer of an order-based question? No: it keeps the order, so comparisons, sorting and "how many smaller" questions are unchanged.

Glossary

Term Meaning Example
Coordinate A position or value on a line position 1000000 on the road
Coordinate compression Replacing each value by its index among the sorted distinct values 100 → 2 in [7, 42, 100, 10^9]
Rank A value's place in sorted order 7 has rank 0
Dense rank Rank where ties share a number and there are no gaps 90 75 90 60 → 3 2 3 1
map A sorted key → value table that stores only inserted keys lamps[x]++
sort Puts a range in increasing order, O(n log n) 7 7 42 100 100 10^9
unique Moves consecutive repeats to the end, returns the new end used inside erase
erase Removes a range of elements from a vector cuts off the repeats
Iterator A pointer-like position inside a container xs.begin()
lower_bound Binary search: first element not less than v index of 100 is 2
Binary search Halving a sorted range to find a value in O(log n) lower_bound
Event point A position where the answer can change l and r + 1
Piece The stretch between two neighbouring points 8..12, length 5
Memory Limit Exceeded (MLE) The program used more memory than allowed 3814 MB array
Lambda A small unnamed function written inline auto id = [&](int v) { ... }

Summary

  • Values up to 10^9 but only 2·10^5 of them: keep only their order.
  • sort, erase(unique(...)), lower_bound − begin: O(n log n), indices 0..m−1, order kept.
  • Forgetting unique makes indices skip (3 0 5 0 2 3).
  • For segments: compress l and r + 1, run the difference array on the points, add piece lengths xs[k+1] − xs[k].
  • Compressing r instead of r + 1 printed 3 1000000 instead of 3 14.

Next episode: two pointers on contest problems: sliding windows in O(n).