Coordinate Compression (Discretization)

Coordinate compression (also called discretization) replaces each value by its rank among all values that matter. When only the relative order of values affects the answer, values up to 10^9 or 10^18 can be squeezed into indices 0..k-1, where k is the number of distinct values. That lets you use arrays, Fenwick trees, segment trees and difference arrays on inputs whose raw values are far too large to index.

Intuition

• Collect every value the algorithm will ever look up, including query values, not only the input array.
• Sort and remove duplicates; the position of a value in that sorted list is its rank.
• Map each original value to its rank with a dictionary (O(1)) or binary search (O(log k)).
• Comparisons between ranks give exactly the same answers as comparisons between the original values, so any order-based logic still works.

What you lose is the distance between values: ranks 3 and 4 may stand for 10 and 10^9. If lengths matter (total covered length, area), keep the sorted coordinate list and treat compressed index i as the elementary segment from xs[i] to xs[i + 1].

Sometimes equal values must still get distinct ranks, for example "rank by value, ties broken by input order". Then sort indices by (value, index) and give out ranks in that order.

When to use it in interviews / OAs

• You want a Fenwick tree or segment tree indexed by value, but values are up to 10^9 or negative: count smaller elements after self, reverse pairs, count of range sums, count inversions online.
• Sweep lines and difference arrays over huge coordinates: total length or area covered by intervals or rectangles, maximum overlap, falling squares, my calendar style booking.
• Rank transform questions: replace each element by its rank.
• Building a dense grid from sparse points so that BFS, prefix sums or union-find can run on it.
• Any offline problem where all queries are known up front, so their values can be compressed together with the data.

Template

Rank each value

def compress(values: list[int]) -> tuple[list[int], list[int]]:
    """Return (ranks, xs): xs is the sorted list of distinct values, xs[ranks[i]] == values[i]."""
    xs = sorted(set(values))
    rank = {v: i for i, v in enumerate(xs)}
    return [rank[v] for v in values], xs

Distinct ranks, ties in input order

def ranks_by_appearance(values: list[int]) -> list[int]:
    order = sorted(range(len(values)), key=lambda i: (values[i], i))
    ranks = [0] * len(values)
    for r, i in enumerate(order):
        ranks[i] = r
    return ranks

Compression plus a Fenwick tree

Count, for every position, how many later elements are smaller. Scan from right to left, keeping a Fenwick tree of counts indexed by compressed value:

def count_smaller_after(nums: list[int]) -> list[int]:
    ranks, xs = compress(nums)
    tree = [0] * (len(xs) + 1)  # Fenwick tree over ranks, 1-based inside

    def add(i: int) -> None:
        i += 1
        while i < len(tree):
            tree[i] += 1
            i += i & -i

    def count_below(i: int) -> int:  # how many inserted ranks are < i
        total = 0
        while i > 0:
            total += tree[i]
            i -= i & -i
        return total

    result = [0] * len(nums)
    for j in range(len(nums) - 1, -1, -1):
        result[j] = count_below(ranks[j])
        add(ranks[j])
    return result

Without compression, tree would need one slot per possible value, which is impossible for values up to 10^9.

Compression that keeps real lengths

Total length covered by a set of half-open intervals [l, r) with coordinates up to 10^18. Compress the endpoints, run a difference array over compressed indices, and add the real length of each elementary segment that is covered:

def covered_length(intervals: list[tuple[int, int]]) -> int:
    xs = sorted({x for interval in intervals for x in interval})
    index = {x: i for i, x in enumerate(xs)}
    diff = [0] * (len(xs) + 1)
    for l, r in intervals:
        diff[index[l]] += 1
        diff[index[r]] -= 1
    total = cover = 0
    for i in range(len(xs) - 1):
        cover += diff[i]
        if cover > 0:  # segment [xs[i], xs[i + 1]) is covered
            total += xs[i + 1] - xs[i]
    return total

The same idea in two dimensions (compress x and y, mark covered cells, add width * height of each covered cell) computes the area of a union of rectangles in O(n^3), or O(n^2 log n) with a segment tree.

Complexity

• Compression: O(n log n) to sort, O(n) to build the dictionary, O(n) space.
• Each lookup: O(1) with a dictionary, O(log k) with bisect_left(xs, v).
• count_smaller_after: O(n log n) overall.
• covered_length: O(n log n), dominated by sorting the endpoints.

Common pitfalls

• Compressing only part of the values. If queries or interval endpoints are not in the compressed set, lookups fail or land on wrong ranks. Compress everything you will look up, which requires knowing the queries in advance (offline).
• Forgetting that gaps disappear. Two compressed neighbors are not neighbors in reality. When lengths or "is there a point strictly between" matter, keep xs and use real differences, or insert extra points (such as x + 1) before compressing.
• Endpoint conventions. With closed intervals [l, r], compress r + 1 instead of r so that the difference array subtracts at the right place.
• Off-by-one with Fenwick trees. They are naturally 1-based; shift ranks by one inside the tree, as above.
• Using list.index to find ranks. That is O(k) per lookup; use a dictionary or bisect.
• Floats as keys. Compress floating-point coordinates only if equal values are bit-identical; otherwise round or scale to integers first.

Interview variations

• Rank transform of an array: exactly compress, returning 1-based ranks.
• Count of smaller numbers after self, reverse pairs, count of range sums: compression plus a Fenwick tree (or merge sort).
• Rectangle area II: 2D compression plus a covered-cell grid or a sweep with a segment tree.
• Falling squares, my calendar III, range module: compress coordinates, then use a segment tree or a difference array.
• Number of flowers in full bloom, points covered by intervals: compress and sweep, or sort starts and ends separately and use binary search.