LeetCode 164: Maximum Gap
A clear explanation of finding the maximum adjacent gap in sorted order using buckets and the pigeonhole principle.
22 notes
A clear explanation of finding the maximum adjacent gap in sorted order using buckets and the pigeonhole principle.
Construct a suffix array by sorting rank pairs with radix or counting sort during the doubling method.
Sort fixed width keys by processing digits from least significant to most significant using a stable inner sort.
Sort integer or string keys by processing one digit, byte, or character position at a time.
Non-comparison sorts: counting, radix, and bucket sort families, string sorting, and suffix array construction.
Sort fixed width keys on a GPU using digit passes, parallel histograms, prefix sums, and scatter operations.
Sort integer keys by processing fixed width digit groups in parallel using counting and prefix sums.
External-memory radix sort that processes large datasets by distributing records into digit-based buckets across multiple passes.
Radix sort for signed integers by transforming values to preserve ordering across negative and positive ranges.
Radix sort for floating-point numbers by transforming their bit representation to preserve numeric order.
LSD radix sort variant that processes keys byte by byte from least significant to most significant.
Radix sort that processes fixed-width keys one byte at a time using 256 counting buckets.
Radix sort specialized for fixed-width machine words using byte or bit extraction for high throughput.
In-place MSD radix string sort that partitions strings by character using American flag style bucket permutation.
MSD radix sort variant that partitions keys by the most significant byte and recursively sorts subarrays.
High performance radix sort variant using cache friendly block partitioning and branchless techniques.
In place binary radix sort that partitions keys by bits from most significant to least significant.
Sort integers by processing bits directly using partitioning instead of counting arrays.
Sort digit based keys by redistributing elements inside the original array with only small auxiliary bucket state.
In place radix sort that partitions elements by digit using cycle leader permutation.
Sort keys by processing the most significant digit first and recursively sorting subarrays.
Sort keys digit by digit using a stable subroutine, achieving linear time for fixed-width integers without any key comparisons.