Coordinate compression

Some problems describe things with very large numbers: events on specific days across a billion-day range, or a grid with columns numbered up to a billion. You cannot build an array with a billion elements, so the numbers as given are unusable directly.

Coordinate compression gets around this. If only a handful of values out of that huge range actually appear in the input, renumber just those values from 0 upward, and run your algorithm on the small renumbered range instead.

When expansion is not possible

Suppose you need to count events by day, and day numbers run from 1 to 1,000,000,000. An array with one slot per day needs a billion slots: too much memory, and too long just to initialize before you have processed a single event.

But if the input only ever mentions 100 distinct days, you never needed a billion slots to begin with. Renumber those 100 days as 0 through 99, and a small array holds everything the problem actually asks about.

The compression process

Collect every large value that appears in the input, sort the unique ones, and give each its position in that sorted order as its new, compressed coordinate. If the input mentions days 5, 8, 100 and 200, sorting them gives the same order, and compressing maps 5 → 0, 8 → 1, 100 → 2, 200 → 3. From here on, the algorithm works with indices 0 through 3 instead of 5, 8, 100 and 200, and every array or lookup it needs only has to be as large as the number of distinct values, not the size of the original range.

A worked example

You are given a list of (day, event_type) pairs across a calendar year, and you want to know how many distinct event types happen on each day that has at least one event.

1n = int(input())2readings = [tuple(map(int, input().split())) for _ in range(n)]3
4unique_days = sorted({day for day, _ in readings})5day_to_compressed = {day: i for i, day in enumerate(unique_days)}6
7event_types = [set() for _ in unique_days]8for day, event_type in readings:9    event_types[day_to_compressed[day]].add(event_type)10
11print("\n".join(str(len(s)) for s in event_types))

5
100 1
200 2
100 3
200 2
150 1

2
1
1

The program reads every reading first, then collects the distinct days that appear and sorts them, and builds day_to_compressed from that sorted list. event_types is a list with one slot per distinct day rather than per possible day, and each reading is filed into event_types[day_to_compressed[day]] as a set, so repeated event types on the same day only count once. Day 100 saw event types 1 and 3, so it prints 2. Day 150 saw only type 1, and day 200 saw type 2 twice, which collapses to one type each, so both print 1. The output lists the three days in sorted order: 2, then 1, then 1.

Why compression works

The algorithm never actually needs the original numbers, it only needs to know which entries are equal and how they are ordered relative to each other. Renumbering by sorted order preserves both facts exactly, so nothing the algorithm depends on is lost. If you need to report a result using the original values afterward, keep the sorted list of unique values around: the compressed index is also its position in that list, so you can look the original value back up whenever you need it.

When you do not need it

Compression is not always necessary. A 1,000-by-1,000 grid has a million cells, and a plain array of a million elements is completely reasonable; there is no huge range to shrink. It also does not help when every value in a huge range is genuinely used: if a problem hands you all of 1 to 1,000,000 and asks you to touch each one, there is no gap between "distinct values used" and "the full range" for compression to exploit, and you cannot do better than processing all million.

Compression earns its keep specifically when the range of possible values is enormous but the values that actually show up in the input are few. A problem with constraints like "coordinates up to 10^9, but at most 2,000 of them appear" is written that way on purpose, to push you toward exactly this technique.

Looking up a compressed index quickly

Building the sorted list of distinct values is only half the job; you also need a fast way to turn an original value into its compressed index. A dictionary built once, mapping each original value to its position, answers that in O(1), which is what the worked example above does with day_to_compressed. When you only need to compress values you already collected up front, a dictionary is the simplest choice.

Sometimes a query asks about a value that never appeared in the original input at all, such as "how many events happened on or before day 175" when 175 was never one of the recorded days. A dictionary has nothing to return for a day it never saw. Python's bisect module handles this: bisect.bisect_right(sorted_days, 175) finds where 175 would sit in the sorted list of distinct days, giving you the count of recorded days at or before it, without needing 175 to be one of the compressed values itself. Reach for a dictionary when every query value is one you already compressed, and for bisect when a query can ask about a value that was never in the original list.

Getting these details right

Collect every value you will need to reference, not just some of them. In an interval problem, that means both the start and the end of every interval; compressing only the starts leaves the ends unmapped, and looking one up later either fails or points at the wrong slot.

Sort before you assign compressed indices. Numbering values in the order they first appear in the input, rather than in sorted order, throws away the one property compression is supposed to preserve: that a smaller original value gets a smaller compressed index.

And once you have built the mapping, use it consistently. Looking up a compressed index with the original value works; trying to use a compressed index as if it were still the original value does not, since the whole point was to replace one with the other.