coordinate-compression

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 699: Falling Squares

Problem Restatement We are given a list of squares falling onto the X-axis. Each square is described by: [left, side_length] The square spans the interval: [left, left + side_length) The square falls vertically until: Situation Result It hits the ground Stops at height 0 It lands on another square Stacks on top After each square falls, we must report the maximum height among all squares so far. The official statement...

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.19 Coordinate Compression

6.19 Coordinate Compression Coordinate compression replaces large or sparse keys with small dense ranks. It preserves order while reducing the value range. This makes range-based algorithms, counting arrays, Fenwick trees, segment trees, and bucketed structures practical on data with large numeric keys. Problem You have values such as: [1000000000, -7, 42, 1000000000, 500000] The values are too large or too sparse to use directly as array indices. You want to...

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Coordinate Compression Sort

Coordinate Compression Sort Coordinate compression sort maps arbitrary values to a dense integer range based on their sorted order, then sorts using these compact indices. It is useful when values are large, sparse, or not directly suitable for counting or radix methods. Problem Given an array $A$ of values, possibly large integers or non-integer comparable items, sort the array efficiently by reducing the value domain. Idea Replace each value with...

#coordinate-compression

LeetCode 699: Falling Squares

6.19 Coordinate Compression

Coordinate Compression Sort