✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-228

Coordinate Compression

Coordinate Compression transforms large or widely separated numerical values into smaller consecutive indices while preserving their relative order.

Explanation

Overview

Coordinate Compression is a technique that replaces each distinct value in a collection with a compact integer rank. It is useful when the original values are too large or too widely spaced for direct indexing, but only their relative order matters.

How it works

Collect all values that may appear in the input or queries.; Sort the collected values.; Remove duplicate values.; Assign each distinct value a consecutive index beginning at zero or one.; Replace each original value with its assigned compressed index.; Use the compressed indices in data structures while retaining the original values when needed.

Key concepts

Relative ordering; Distinct values; Sorting; Rank assignment; Index mapping; Memory-efficient representation

Time complexity

operation: Sorting values; complexity: O(n log n); operation: Removing duplicates; complexity: O(n) after sorting; operation: Building the mapping; complexity: O(n); operation: Replacing original values; complexity: O(n) with efficient mapping lookup; operation: Overall; complexity: O(n log n)

Space complexity

O(n) for sorted values, unique values, mappings, and compressed results.

Example

originalValues: 1000000; -50; sortedUniqueValues: -50; 25; mapping: original: -50; compressed: 0; original: 25; compressed: 1; compressedArray: 3; 0; explanation: The original numerical values are replaced by small ranks while preserving their ordering and equality relationships.

Applications

Fenwick Tree indexing; Segment Tree indexing; Inversion counting; Offline range queries; Large-coordinate interval problems; Computational geometry

Example or application

Original Values

  • 1000000

  • -50

  • 700

  • 1000000

  • 25

Sorted Unique Values

  • -50

  • 25

  • 700

  • 1000000

Mapping

OriginalCompressed

-50

0

25

1

700

2

1000000

3

Compressed Array

  • 3

  • 0

  • 2

  • 3

  • 1

Explanation

The original numerical values are replaced by small ranks while preserving their ordering and equality relationships.

Definition

Coordinate Compression is a technique that replaces each distinct value in a collection with a compact integer rank. It is useful when the original values are too large or too widely spaced for direct indexing, but only their relative order matters.

Why It Is Needed

An algorithm may need an array indexed by values that are extremely large or negative. Allocating an array across the entire numerical range would waste memory. Coordinate compression maps the distinct values to a small consecutive range, allowing efficient use of arrays, Fenwick Trees, Segment Trees, and other index-based structures.

How It Works

  • Collect all values that may appear in the input or queries.

  • Sort the collected values.

  • Remove duplicate values.

  • Assign each distinct value a consecutive index beginning at zero or one.

  • Replace each original value with its assigned compressed index.

  • Use the compressed indices in data structures while retaining the original values when needed.

Implementation

Language

Pseudocode

Code

  • function compressCoordinates(values):

  • sortedValues = sort(values)

  • uniqueValues = removeDuplicates(sortedValues)

  • mapping = empty map

  • for i from 0 to length(uniqueValues) - 1:

  • mapping[uniqueValues[i]] = i

  • compressed = empty list

  • for value in values:

  • compressed.append(mapping[value])

  • return compressed, uniqueValues

Time Complexity

OperationComplexity

Sorting values

O(n log n)

Removing duplicates

O(n) after sorting

Building the mapping

O(n)

Replacing original values

O(n) with efficient mapping lookup

Overall

O(n log n)

Space Complexity

O(n) for sorted values, unique values, mappings, and compressed results.

Key Concepts

  • Relative ordering

  • Distinct values

  • Sorting

  • Rank assignment

  • Index mapping

  • Memory-efficient representation

  • Value-to-index conversion

Advantages

  • Reduces a large numerical range to a compact index range.

  • Allows array-based data structures to handle large coordinates.

  • Preserves relative order and equality relationships.

  • Works well with Fenwick Trees and Segment Trees.

  • Can significantly reduce memory requirements.

Limitations

  • The mapping must include every value that may be queried or updated.

  • New values may require rebuilding or extending the compression structure.

  • Compressed differences do not preserve original numerical distances.

  • Additional mapping information may be needed to recover original values.

Applications

  • Fenwick Tree indexing

  • Segment Tree indexing

  • Inversion counting

  • Offline range queries

  • Large-coordinate interval problems

  • Computational geometry

  • Competitive programming

Related Topics

  • Fenwick Trees

  • Segment Trees

  • Sweep Line Algorithms

  • Sorting Algorithms

  • Order Statistics

Practice Questions

QuestionAnswer

What does Coordinate Compression preserve?

The relative ordering and equality of distinct values.

Why is Coordinate Compression useful?

It replaces large or sparse values with compact consecutive indices.

Does coordinate compression preserve the actual distance between values?

No. It preserves ordering, not the original numerical differences.

What is the typical time complexity of coordinate compression?

O(n log n), mainly because of sorting.

Learning Objectives

  • Explain the central idea and purpose of coordinate compression.

  • Identify the assumptions, inputs, and conditions relevant to coordinate compression.

  • Evaluate an application of coordinate compression for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Specialized Algorithms and Computational Topics

Suggest a correction or source · More in Algorithms & Data Structures