Using Coordinate Compression

1. Applying Coordinate Compression

Coordinate compression is a technique used to reduce the space complexity of algorithms that work with large coordinate systems by mapping large coordinates to a smaller, contiguous range.

Step	Description	Action
1. Collect All Coordinates	Extract all unique x and y coordinates from the input data.	Iterate through all points or intervals and collect distinct x and y values.
2. Sort Coordinates	Sort the collected coordinates in ascending order.	Use a sorting algorithm to arrange all unique x and y values in increasing order.
3. Map Coordinates	Create a mapping from original coordinates to compressed indices.	Assign each unique coordinate a new index in the range [0, n), where n is the number of unique coordinates.
4. Apply Mapping	Replace original coordinates with their compressed indices in the data structure.	Update all points or intervals to use the new indices instead of original coordinates.

Example: Compressing 2D Points

const points = [
  { x: 1000, y: 2000 },
  { x: 5000, y: 3000 },
  { x: 1000, y: 3000 }
];

// Step 1: Collect all unique coordinates
const xCoords = new Set(points.map(p => p.x));
const yCoords = new Set(points.map(p => p.y));

// Step 2: Sort coordinates
const sortedX = [...xCoords].sort((a, b) => a - b);
const sortedY = [...yCoords].sort((a, b) => a - b);

// Step 3: Map coordinates to indices
const xMap = new Map(sortedX.map((coord, index) => [coord, index]));
const yMap = new Map(sortedY.map((coord, index) => [coord, index]));

// Step 4: Apply mapping to points
const compressedPoints = points.map(p => ({
  x: xMap.get(p.x),
  y: yMap.get(p.y)
}));

console.log(compressedPoints); // [{ x: 0, y: 0 }, { x: 1, y: 1 }, { x: 0, y: 1 }]

Note: Coordinate compression is particularly useful in problems involving 2D grids or spatial data where the actual coordinate values are large but only a few distinct values are used.

2. Collecting Unique Coordinates

Operation	Description	Time Complexity	Space Complexity
Scan X and Y coordinates	Extract all unique x and y values from input points or intervals	`O(n log n)`	`O(n)`
Sort coordinates	Sort unique x and y values to prepare for mapping	`O(n log n)`	`O(n)`
Map to compressed indices	Assign compressed indices (0, 1, 2, ...) to sorted unique coordinates	`O(n)`	`O(n)`

Example: Collecting Unique Coordinates from Points

const points = [
  { x: 10, y: 20 },
  { x: 30, y: 40 },
  { x: 10, y: 50 },
  { x: 60, y: 20 }
];

// Step 1: Collect all unique x and y values
const uniqueX = new Set(points.map(p => p.x));
const uniqueY = new Set(points.map(p => p.y));

// Step 2: Sort them
const sortedX = Array.from(uniqueX).sort((a, b) => a - b);
const sortedY = Array.from(uniqueY).sort((a, b) => a - b);

// Step 3: Map to compressed indices
const xMap = new Map(sortedX.map((val, idx) => [val, idx]));
const yMap = new Map(sortedY.map((val, idx) => [val, idx]));

console.log(sortedX); // [10, 30, 60]
console.log(sortedY); // [20, 40, 50]
console.log(xMap.get(10)); // 0
console.log(yMap.get(20)); // 0

Note: Coordinate compression is useful when the coordinate space is much larger than the number of actual points or intervals, allowing efficient use of data structures like 2D arrays or segment trees.

3. Sorting Coordinates

Operation	Description	Time Complexity	Space Complexity
Sort 1D Coordinates	Arrange a list of coordinate values in ascending or descending order	`O(n log n)`	`O(1)` if in-place, `O(n)` otherwise
Sort 2D Coordinates	Sort points by x-coordinate first, then y-coordinate (stable sort)	`O(n log n)`	`O(1)` if in-place, `O(n)` otherwise
Custom Sort Order	Sort based on custom criteria (e.g., distance from origin)	`O(n log n)`	`O(1)` if in-place, `O(n)` otherwise

Example: Sorting 2D Coordinates by X

const points = [
  { x: 3, y: 4 },
  { x: 1, y: 2 },
  { x: 5, y: 6 }
];

points.sort((a, b) => a.x - b.x);

console.log(points);
// Output:
// [
//   { x: 1, y: 2 },
//   { x: 3, y: 4 },
//   { x: 5, y: 6 }
// ]

Example: Sorting by Distance from Origin

const points = [
  { x: 3, y: 4 },
  { x: 1, y: 2 },
  { x: 0, y: 1 }
];

points.sort((a, b) => {
  const distA = Math.sqrt(a.x * a.x + a.y * a.y);
  const distB = Math.sqrt(b.x * b.x + b.y * b.y);
  return distA - distB;
});

console.log(points);
// Output:
// [
//   { x: 0, y: 1 },
//   { x: 1, y: 2 },
//   { x: 3, y: 4 }
// ]

4. Creating Compressed Mapping

Step	Description	Implementation
1. Collect Coordinates	Extract all unique x and y coordinates from the input data.	`const points = [[1, 2], [3, 4], [1, 4], [5, 6]]; const xCoords = new Set(points.map(p => p[0])); const yCoords = new Set(points.map(p => p[1]));`
2. Sort Coordinates	Sort the unique coordinates to establish a mapping order.	`const sortedX = Array.from(xCoords).sort((a, b) => a - b); const sortedY = Array.from(yCoords).sort((a, b) => a - b);`
3. Build Mapping	Create a mapping from original coordinates to compressed indices.	`const xMap = new Map(sortedX.map((coord, index) => [coord, index])); const yMap = new Map(sortedY.map((coord, index) => [coord, index]));`
4. Apply Compression	Transform original coordinates to compressed indices.	`const compressedPoints = points.map(([x, y]) => [ xMap.get(x), yMap.get(y) ]);`

Example: Coordinate Compression

const points = [[1, 2], [3, 4], [1, 4], [5, 6]];
const xCoords = new Set(points.map(p => p[0]));
const yCoords = new Set(points.map(p => p[1]));

const sortedX = Array.from(xCoords).sort((a, b) => a - b);
const sortedY = Array.from(yCoords).sort((a, b) => a - b);

const xMap = new Map(sortedX.map((coord, index) => [coord, index]));
const yMap = new Map(sortedY.map((coord, index) => [coord, index]));

const compressedPoints = points.map(([x, y]) => [
  xMap.get(x),
  yMap.get(y)
]);

console.log(compressedPoints); // [[0, 0], [1, 1], [0, 1], [2, 2]]

5. Mapping Original to Compressed

Original Coordinate	Compressed Coordinate	Notes
10	`0`	First unique value mapped to 0
25	`1`	Second unique value mapped to 1
50	`2`	Third unique value mapped to 2
75	`3`	Fourth unique value mapped to 3
100	`4`	Last unique value mapped to 4

Example: Coordinate Compression Mapping

const originalCoords = [10, 25, 50, 75, 100];
const uniqueCoords = [...new Set(originalCoords)].sort((a, b) => a - b);
const mapping = {};
uniqueCoords.forEach((coord, index) => {
  mapping[coord] = index;
});
console.log(mapping); // {10: 0, 25: 1, 50: 2, 75: 3, 100: 4}

6. Solving Large Coordinate Problems

Coordinate compression is a powerful technique for handling large coordinate spaces efficiently, particularly in computational geometry and grid-based problems. It reduces the effective size of coordinates by mapping them to a smaller, contiguous range while preserving their relative order.

Problem Type	Description	Solution Approach	Time Complexity
Large Coordinate Space	Input coordinates span a very large range (e.g., 10^9), making direct indexing or grid-based solutions infeasible.	Compress coordinates to a smaller range using mapping techniques.	O(n log n) for sorting + O(n) for compression
Range Queries	Need to perform queries or updates over a large coordinate space, such as counting points in a rectangle.	Use compressed coordinates to build a 2D segment tree or Fenwick Tree.	O(log² n) for queries

Example: Compressing 2D Coordinates

const points = [
  { x: 1000000000, y: 2000000000 },
  { x: 1000000001, y: 2000000001 },
  { x: 1000000002, y: 2000000002 }
];

// Step 1: Collect all unique x and y coordinates
const xs = new Set(points.map(p => p.x));
const ys = new Set(points.map(p => p.y));

// Step 2: Sort and create mapping
const sortedX = [...xs].sort((a, b) => a - b);
const sortedY = [...ys].sort((a, b) => a - b);

const xMap = new Map(sortedX.map((x, i) => [x, i]));
const yMap = new Map(sortedY.map((y, i) => [y, i]));

// Step 3: Compress coordinates
const compressedPoints = points.map(p => ({
  x: xMap.get(p.x),
  y: yMap.get(p.y)
}));

console.log(compressedPoints); // [{x: 0, y: 0}, {x: 1, y: 1}, {x: 2, y: 2}]

Note: Coordinate compression is particularly useful in problems involving large coordinate ranges but a small number of distinct values, such as point counting or range queries in grids.

Key Benefits of Coordinate Compression

Reduces space complexity by mapping large coordinates to small indices.
Enables efficient use of data structures like segment trees or Fenwick trees.
Preserves relative ordering between coordinates.

7. Applying to 2D Problems

Coordinate compression is particularly useful in 2D problems where you have a large number of points or rectangles with integer coordinates. By compressing the coordinates, you can reduce the search space and improve performance.

Problem Type	Description	Approach	Time Complexity
Point Updates	Updating values at specific 2D coordinates	Compress X and Y coordinates separately, use compressed indices in a 2D segment tree or Fenwick tree	O(log²n)
Range Queries	Querying sum or max/min in a rectangular region	Compress coordinates, use compressed indices for 2D range queries	O(log²n)
Rectangle Overlaps	Detecting overlaps between rectangles	Compress coordinates, use sweep line algorithm with compressed indices	O(n log n)

Example: Point Updates in 2D Grid

class CoordinateCompressed2D {
  constructor(points) {
    this.compressedX = this.compressCoordinates(points.map(p => p.x));
    this.compressedY = this.compressCoordinates(points.map(p => p.y));
    this.tree = new SegmentTree2D(this.compressedX.length, this.compressedY.length);
  }

  compressCoordinates(coords) {
    const sorted = [...new Set(coords)].sort((a, b) => a - b);
    const map = new Map();
    sorted.forEach((coord, i) => map.set(coord, i));
    return map;
  }

  update(x, y, value) {
    const xIdx = this.compressedX.get(x);
    const yIdx = this.compressedY.get(y);
    this.tree.update(xIdx, yIdx, value);
  }

  query(x1, y1, x2, y2) {
    const x1Idx = this.compressedX.get(x1);
    const y1Idx = this.compressedY.get(y1);
    const x2Idx = this.compressedX.get(x2);
    const y2Idx = this.compressedY.get(y2);
    return this.tree.query(x1Idx, y1Idx, x2Idx, y2Idx);
  }
}

// Example usage:
const points = [{x: 10, y: 20}, {x: 30, y: 40}];
const compressedGrid = new CoordinateCompressed2D(points);
compressedGrid.update(10, 20, 5);
console.log(compressedGrid.query(10, 20, 30, 40)); // 5

Note: Coordinate compression is especially effective in problems involving sparse data or large coordinate ranges where most coordinates are unused.

8. Implementing with Segment Tree

Example: Coordinate Compression with Segment Tree

class SegmentTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(4 * size).fill(0);
  }

  update(index, value) {
    this.updateHelper(0, 0, this.size - 1, index, value);
  }

  updateHelper(node, start, end, index, value) {
    if (start === end) {
      this.tree[node] += value;
      return;
    }

    const mid = Math.floor((start + end) / 2);
    if (index <= mid) {
      this.updateHelper(2 * node + 1, start, mid, index, value);
    } else {
      this.updateHelper(2 * node + 2, mid + 1, end, index, value);
    }
    this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
  }

  query(left, right) {
    return this.queryHelper(0, 0, this.size - 1, left, right);
  }

  queryHelper(node, start, end, left, right) {
    if (right < start || left > end) return 0;
    if (left <= start && end <= right) return this.tree[node];

    const mid = Math.floor((start + end) / 2);
    return this.queryHelper(node * 2 + 1, start, mid, left, right) +
           this.queryHelper(node * 2 + 2, mid + 1, end, left, right);
  }
}

// Coordinate compression example
const coordinates = [10, 50, 30, 70, 20];
const uniqueCoords = [...new Set(coordinates)].sort((a, b) => a - b);
const coordinateMap = new Map();
uniqueCoords.forEach((coord, index) => {
  coordinateMap.set(coord, index);
});

// Use compressed indices in segment tree
const segTree = new SegmentTree(uniqueCoords.length);
coordinates.forEach(coord => {
  const index = coordinateMap.get(coord);
  segTree.update(index, 1);
});

// Query range [20, 50]
const left = coordinateMap.get(20);
const right = coordinateMap.get(50);
console.log(segTree.query(left, right)); // Output: 2

Operation	Description	Time Complexity	Space Complexity
update(index, value)	Updates the value at a given index in the segment tree	O(log n)	O(n)
query(left, right)	Queries the sum of values in a range [left, right]	O(log n)	O(n)

Note: Coordinate compression reduces the effective size of the coordinate space, allowing efficient use of segment trees for range queries.

9. Implementing with Fenwick Tree

A Fenwick Tree (also known as a Binary Indexed Tree) is a data structure that efficiently supports prefix sum queries and point updates. It's particularly useful in problems involving coordinate compression where we need to handle range queries or updates on a compressed set of coordinates.

Operation	Description	Time Complexity	Space Complexity
Build	Constructs the Fenwick Tree from an array of values.	O(n log n)	O(n)
Query Prefix Sum	Computes the sum of elements from index 0 to i.	O(log n)	O(1)
Update Point	Updates the value at a specific index.	O(log n)	O(1)

Example: Building and Querying a Fenwick Tree

class FenwickTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }

  update(index, delta) {
    while (index <= this.size) {
      this.tree[index] += delta;
      index += index & (-index);
    }
  }

  query(prefixLength) {
    let sum = 0;
    while (prefixLength > 0) {
      sum += this.tree[prefixLength];
      prefixLength -= prefixLength & (-prefixLength);
    }
    return sum;
  }

  rangeSum(left, right) {
    return this.query(right) - this.query(left - 1);
  }
}

// Example usage:
const arr = [1, 3, 5, 7, 9, 11];
const ft = new FenwickTree(arr.length);
for (let i = 0; i < arr.length; i++) {
  ft.update(i + 1, arr[i]);
}

console.log(ft.query(3)); // Sum from index 0 to 2 = 1 + 3 + 5 = 9
console.log(ft.rangeSum(2, 4)); // Sum from index 2 to 4 = 5 + 7 + 9 = 21

Note: The Fenwick Tree is particularly efficient for problems where we have frequent updates and prefix sum queries. When combined with coordinate compression, it allows us to manage large ranges efficiently.

10. Handling Queries

Query Type	Description	Approach	Time Complexity
Range Query	Find sum or count in a range [l, r]	Use compressed coordinates with segment tree or binary indexed tree	O(log n)
Point Update	Update value at a specific coordinate	Update compressed indices in segment tree or BIT	O(log n)
Range Update	Update values in a range [l, r]	Use lazy propagation with segment tree	O(log n)

Example: Range Sum Query

const n = 100000;
const segTree = new SegmentTree(n);
const coords = [1, 3, 5, 7, 9];
const compressed = compress(coords);
segTree.update(compressed[1], 5); // Update coordinate 1 with value 5
segTree.update(compressed[3], 10); // Update coordinate 3 with value 10
const sum = segTree.rangeSum(compressed[1], compressed[4]); // Sum from 1 to 9

Note: Coordinate compression is essential for handling large coordinate spaces efficiently.