Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Counting, Bucket and Radix Sort

Editorial

Two million scores

Two million exam scores, each from 0 to 100, to sort. The library sort compares them; with only 101 possible scores you can instead count how many students got each one and write them out in order. Both, timed:

#include <bits/stdc++.h>
using namespace std;

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}

int main() {
    vector<int> scores(2000000);
    for (int& s : scores) s = randomBelow(101);      // 0 to 100
    vector<int> a = scores;
    auto start = chrono::steady_clock::now();
    sort(a.begin(), a.end());
    double library = chrono::duration<double, milli>(chrono::steady_clock::now() - start).count();
    start = chrono::steady_clock::now();
    vector<int> count(101), out;                     // how many of each score, then each score that many times
    out.reserve(scores.size());
    for (int s : scores) count[s]++;
    for (int s = 0; s <= 100; s++) out.insert(out.end(), count[s], s);
    double counting = chrono::duration<double, milli>(chrono::steady_clock::now() - start).count();
    printf("library %.1f ms, counting %.1f ms, same: %s\n", library, counting, out == a ? "true" : "false");
}

// library 73.6 ms, counting 6.5 ms, same: true
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums

import time

scores = [random_below(101) for _ in range(2000000)]   # 0 to 100
start = time.perf_counter()
a = sorted(scores)
library = (time.perf_counter() - start) * 1000
start = time.perf_counter()
count = [0] * 101                     # how many of each score, then each score that many times
for s in scores:
    count[s] += 1
out = []
for s in range(101):
    out.extend([s] * count[s])
counting = (time.perf_counter() - start) * 1000
print(f"library {library:.1f} ms, counting {counting:.1f} ms, same: {str(out == a).lower()}")

# library 256.1 ms, counting 246.5 ms, same: true
import java.util.*;

public class Main {
    static int seed = (int) 2463534242L;

    static int randomBelow(int bound) {          // xorshift: the same numbers in every language
        seed ^= seed << 13;
        seed ^= seed >>> 17;
        seed ^= seed << 5;
        return Integer.remainderUnsigned(seed, bound);
    }

    static int[] shuffled(int n) {               // 0 .. n-1 in a random order
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = randomBelow(i + 1), t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] scores = new int[2000000];
        for (int i = 0; i < scores.length; i++) scores[i] = randomBelow(101);   // 0 to 100
        int[] a = scores.clone();
        long start = System.nanoTime();
        Arrays.sort(a);
        double library = (System.nanoTime() - start) / 1e6;
        start = System.nanoTime();
        int[] count = new int[101], out = new int[scores.length];   // how many of each, then each that many times
        for (int s : scores) count[s]++;
        int k = 0;
        for (int s = 0; s <= 100; s++) for (int c = 0; c < count[s]; c++) out[k++] = s;
        double counting = (System.nanoTime() - start) / 1e6;
        System.out.printf("library %.1f ms, counting %.1f ms, same: %b%n", library, counting, Arrays.equals(out, a));
    }
}

// library 173.3 ms, counting 32.5 ms, same: true
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

const scores = Array.from({ length: 2000000 }, () => randomBelow(101));   // 0 to 100
let start = process.hrtime.bigint();
const a = scores.slice().sort((x, y) => x - y);
const library = Number(process.hrtime.bigint() - start) / 1e6;
start = process.hrtime.bigint();
const count = new Array(101).fill(0), out = [];   // how many of each score, then each score that many times
for (const s of scores) count[s]++;
for (let s = 0; s <= 100; s++) for (let c = 0; c < count[s]; c++) out.push(s);
const counting = Number(process.hrtime.bigint() - start) / 1e6;
console.log(`library ${library.toFixed(1)} ms, counting ${counting.toFixed(1)} ms, same: ${out.every((v, i) => v === a[i])}`);

// library 929.7 ms, counting 149.0 ms, same: true

Counting took 6.5 ms in C++ against the library's 74 ms, 11 times faster; Java and JavaScript were 5 and 6 times faster. Python came out level, 256 ms against 246 ms: its library sort runs in C, and the counting loop runs as Python, so the better O(n) pays for a slower step.

This lesson is about the sorts that don't compare: counting, radix and bucket sort, and Maximum Gap, which asks for exactly what they make possible, linear time. First, why comparing can't.

Two dashed panels. Left, counting sort, keys 0 to 3: the cards 3a 1b 3c 0d 1e, coloured by key; count, under keys 0 to 3: 1 2 0 2, the 0 pale; ends: 1 3 3 5; placed, in slots 0 to 4: 0d 1b 1e 3a 3c, with 1b and 1e ringed in green; 1b before 1e, as they came: stable. Right, no comparisons: 1. count each key: 1 2 0 2; 2. add them up: where each key's run ends: 1 3 3 5; 3. from the right, each card takes its key's last free slot; O(n + k) time and a count per key. Focal line: use the key as an index: count, add up, place. Title: count instead of compare.

The limit of comparing

A sort that only compares learns one yes or no per comparison. n values can arrive in n! orders, and it has to tell every one of them apart, since each needs different moves; each answer at best halves the orders still possible. So some order needs at least log₂ n! comparisons, which is about n log₂ n − 1.44 n:

#include <bits/stdc++.h>
using namespace std;

int main() {                              // ceil(log2(n!)): the comparisons some order of n values needs
    for (int n : {8, 1000}) {
        double bits = 0;
        for (int k = 2; k <= n; k++) bits += log2(k);
        printf("%d values: at least %d comparisons for some order\n", n, (int) ceil(bits));
    }
}

// 8 values: at least 16 comparisons for some order
// 1000 values: at least 8530 comparisons for some order
import math

for n in (8, 1000):                   # ceil(log2(n!)): the comparisons some order of n values needs
    bits = sum(math.log2(k) for k in range(2, n + 1))
    print(f"{n} values: at least {math.ceil(bits)} comparisons for some order")

# 8 values: at least 16 comparisons for some order
# 1000 values: at least 8530 comparisons for some order
public class Main {
    public static void main(String[] args) {   // ceil(log2(n!)): the comparisons some order of n values needs
        for (int n : new int[]{8, 1000}) {
            double bits = 0;
            for (int k = 2; k <= n; k++) bits += Math.log(k) / Math.log(2);
            System.out.println(n + " values: at least " + (int) Math.ceil(bits) + " comparisons for some order");
        }
    }
}

// 8 values: at least 16 comparisons for some order
// 1000 values: at least 8530 comparisons for some order
for (const n of [8, 1000]) {             // ceil(log2(n!)): the comparisons some order of n values needs
    let bits = 0;
    for (let k = 2; k <= n; k++) bits += Math.log2(k);
    console.log(`${n} values: at least ${Math.ceil(bits)} comparisons for some order`);
}

// 8 values: at least 16 comparisons for some order
// 1000 values: at least 8530 comparisons for some order

On the 1,000 shuffled values of Introduction to Sorting, merge sort made 8,707 comparisons, close to that floor. No comparison sort beats O(n log n) in the worst case, which is why the sorts below don't compare at all: they read the keys as numbers and use them as positions.

Counting sort

Keys from 0 to k − 1: count each key, then turn the counts into where each key's run ends, a prefix sum. Then walk the input from the right and put each item at the last free slot of its key. Going from the right keeps items with equal keys in the order they came, so counting sort is stable, and radix sort below depends on it:

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<pair<int, char>> cards = {{3, 'a'}, {1, 'b'}, {3, 'c'}, {0, 'd'}, {1, 'e'}};   // (key, name)
    int k = 4;                                        // keys are 0 to k - 1
    vector<int> count(k);
    for (auto& c : cards) count[c.first]++;
    printf("count:");
    for (int x : count) printf(" %d", x);
    for (int v = 1; v < k; v++) count[v] += count[v - 1];   // now: how many keys are <= v
    printf("\nends:");
    for (int x : count) printf(" %d", x);
    vector<pair<int, char>> out(cards.size());
    for (int i = cards.size() - 1; i >= 0; i--)       // from the right, so equal keys keep their order
        out[--count[cards[i].first]] = cards[i];
    printf("\nsorted:");
    for (auto& c : out) printf(" %d%c", c.first, c.second);
    printf("\n");
}

// count: 1 2 0 2
// ends: 1 3 3 5
// sorted: 0d 1b 1e 3a 3c
cards = [(3, "a"), (1, "b"), (3, "c"), (0, "d"), (1, "e")]   # (key, name)
k = 4                                 # keys are 0 to k - 1
count = [0] * k
for key, _ in cards:
    count[key] += 1
print("count:", *count)
for v in range(1, k):                 # now: how many keys are <= v
    count[v] += count[v - 1]
print("ends:", *count)
out = [None] * len(cards)
for card in reversed(cards):          # from the right, so equal keys keep their order
    count[card[0]] -= 1
    out[count[card[0]]] = card
print("sorted:", *(f"{key}{name}" for key, name in out))

# count: 1 2 0 2
# ends: 1 3 3 5
# sorted: 0d 1b 1e 3a 3c
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] keys = {3, 1, 3, 0, 1};
        char[] names = {'a', 'b', 'c', 'd', 'e'};      // card i is keys[i], names[i]
        int k = 4;                                     // keys are 0 to k - 1
        int[] count = new int[k];
        for (int key : keys) count[key]++;
        System.out.println("count: " + join(count));
        for (int v = 1; v < k; v++) count[v] += count[v - 1];   // now: how many keys are <= v
        System.out.println("ends: " + join(count));
        int[] outKeys = new int[keys.length];
        char[] outNames = new char[keys.length];
        for (int i = keys.length - 1; i >= 0; i--) {   // from the right, so equal keys keep their order
            int at = --count[keys[i]];
            outKeys[at] = keys[i];
            outNames[at] = names[i];
        }
        StringBuilder line = new StringBuilder("sorted:");
        for (int i = 0; i < keys.length; i++) line.append(" ").append(outKeys[i]).append(outNames[i]);
        System.out.println(line);
    }

    static String join(int[] xs) {
        StringJoiner j = new StringJoiner(" ");
        for (int x : xs) j.add(String.valueOf(x));
        return j.toString();
    }
}

// count: 1 2 0 2
// ends: 1 3 3 5
// sorted: 0d 1b 1e 3a 3c
const cards = [[3, "a"], [1, "b"], [3, "c"], [0, "d"], [1, "e"]];   // [key, name]
const k = 4;                              // keys are 0 to k - 1
const count = new Array(k).fill(0);
for (const [key] of cards) count[key]++;
console.log("count: " + count.join(" "));
for (let v = 1; v < k; v++) count[v] += count[v - 1];   // now: how many keys are <= v
console.log("ends: " + count.join(" "));
const out = new Array(cards.length);
for (let i = cards.length - 1; i >= 0; i--)   // from the right, so equal keys keep their order
    out[--count[cards[i][0]]] = cards[i];
console.log("sorted: " + out.map(([key, name]) => key + name).join(" "));

// count: 1 2 0 2
// ends: 1 3 3 5
// sorted: 0d 1b 1e 3a 3c

Key 1 ends at 3, so the walk from the right puts 1e in slot 2 and then 1b in slot 1: b before e, as they came. Time O(n + k), space O(n + k): a count per possible key. That's the catch: with keys up to 10⁹, the counts alone are 10⁹ cells, 4 GB of 32-bit ints, however few values there are.

Radix sort

For bigger keys, sort by one digit at a time with that stable counting sort, least significant digit first: ones, then tens, then hundreds. Each pass is a counting sort with k = 10:

Two dashed panels. Left, one stable pass per digit: four rows of eight tiles, each number in three digits with leading zeros pale. Start: 170 45 75 90 802 24 2 66. Ones, the ones digit in amber: 170 90 802 2 24 45 75 66. Tens, the tens digit in amber: 802 2 24 45 66 170 75 90. Hundreds, in green with the hundreds digit in amber: 2 24 45 66 75 90 170 802. Right, why it works: each pass is a stable counting sort on one digit; 802 and 2 share the tens digit 0: the ones pass's order stays; d digits, base b: O(d (n + b)); 3 passes, base 10. Focal line: last digit first; stability keeps the earlier passes. Title: LSD radix, digit by digit.
#include <bits/stdc++.h>
using namespace std;

void byDigit(vector<int>& a, int place) {          // a stable counting sort on one decimal digit
    vector<int> count(10), out(a.size());
    for (int v : a) count[v / place % 10]++;
    for (int d = 1; d < 10; d++) count[d] += count[d - 1];
    for (int i = a.size() - 1; i >= 0; i--) out[--count[a[i] / place % 10]] = a[i];
    a = out;
}

int main() {
    vector<int> a = {170, 45, 75, 90, 802, 24, 2, 66};
    int largest = *max_element(a.begin(), a.end());
    for (int place = 1; largest / place > 0; place *= 10) {   // ones, then tens, then hundreds
        byDigit(a, place);
        printf("by the %ss:", place == 1 ? "one" : place == 10 ? "ten" : "hundred");
        for (int v : a) printf(" %d", v);
        printf("\n");
    }
}

// by the ones: 170 90 802 2 24 45 75 66
// by the tens: 802 2 24 45 66 170 75 90
// by the hundreds: 2 24 45 66 75 90 170 802
def by_digit(a, place):                # a stable counting sort on one decimal digit
    count = [0] * 10
    for v in a:
        count[v // place % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]
    out = [0] * len(a)
    for v in reversed(a):
        count[v // place % 10] -= 1
        out[count[v // place % 10]] = v
    return out


a = [170, 45, 75, 90, 802, 24, 2, 66]
place = 1
while max(a) // place > 0:            # ones, then tens, then hundreds
    a = by_digit(a, place)
    print(f"by the {({1: 'one', 10: 'ten'}).get(place, 'hundred')}s:", *a)
    place *= 10

# by the ones: 170 90 802 2 24 45 75 66
# by the tens: 802 2 24 45 66 170 75 90
# by the hundreds: 2 24 45 66 75 90 170 802
import java.util.*;

public class Main {
    static int[] byDigit(int[] a, int place) {   // a stable counting sort on one decimal digit
        int[] count = new int[10], out = new int[a.length];
        for (int v : a) count[v / place % 10]++;
        for (int d = 1; d < 10; d++) count[d] += count[d - 1];
        for (int i = a.length - 1; i >= 0; i--) out[--count[a[i] / place % 10]] = a[i];
        return out;
    }

    public static void main(String[] args) {
        int[] a = {170, 45, 75, 90, 802, 24, 2, 66};
        int largest = Arrays.stream(a).max().getAsInt();
        for (int place = 1; largest / place > 0; place *= 10) {   // ones, then tens, then hundreds
            a = byDigit(a, place);
            StringBuilder line = new StringBuilder("by the " + (place == 1 ? "one" : place == 10 ? "ten" : "hundred") + "s:");
            for (int v : a) line.append(" ").append(v);
            System.out.println(line);
        }
    }
}

// by the ones: 170 90 802 2 24 45 75 66
// by the tens: 802 2 24 45 66 170 75 90
// by the hundreds: 2 24 45 66 75 90 170 802
function byDigit(a, place) {              // a stable counting sort on one decimal digit
    const count = new Array(10).fill(0), out = new Array(a.length);
    for (const v of a) count[Math.floor(v / place) % 10]++;
    for (let d = 1; d < 10; d++) count[d] += count[d - 1];
    for (let i = a.length - 1; i >= 0; i--) out[--count[Math.floor(a[i] / place) % 10]] = a[i];
    return out;
}

let a = [170, 45, 75, 90, 802, 24, 2, 66];
const largest = Math.max(...a);
for (let place = 1; Math.floor(largest / place) > 0; place *= 10) {   // ones, then tens, then hundreds
    a = byDigit(a, place);
    console.log(`by the ${place === 1 ? "one" : place === 10 ? "ten" : "hundred"}s: ${a.join(" ")}`);
}

// by the ones: 170 90 802 2 24 45 75 66
// by the tens: 802 2 24 45 66 170 75 90
// by the hundreds: 2 24 45 66 75 90 170 802

After the tens pass, 24, 45 and 66 are in order, and so are 170, 75 and 90 by their last two digits: values with the same tens digit kept the order the ones pass gave them. That's why each pass must be stable. After the last digit the whole thing is sorted. d digits in base b cost O(d (n + b)): 32-bit ints in base 256 are four passes of O(n + 256), linear in n.

Most significant digit first works too, splitting into buckets by the first digit and sorting each recursively; it suits strings, where it can stop at the first differing character. Negative numbers need one more step: offset every value by the minimum first, or sort the negatives separately.

Bucket sort

When values are spread evenly over a range, divide the range into n buckets, drop each value into its bucket by arithmetic, sort each bucket, and read the buckets in order:

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<double> a = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};   // spread over [0, 1)
    int n = a.size();
    vector<vector<double>> buckets(n);              // n buckets, each a tenth wide
    for (double v : a) buckets[(int) (v * n)].push_back(v);
    vector<double> out;
    for (int b = 0; b < n; b++) {
        sort(buckets[b].begin(), buckets[b].end()); // each bucket is short: any sort will do
        if (buckets[b].empty()) continue;
        printf("bucket %d:", b);
        for (double v : buckets[b]) printf(" %.2f", v), out.push_back(v);
        printf("\n");
    }
    printf("sorted:");
    for (double v : out) printf(" %.2f", v);
    printf("\n");
}

// bucket 1: 0.12 0.17
// bucket 2: 0.21 0.23 0.26
// bucket 3: 0.39
// bucket 6: 0.68
// bucket 7: 0.72 0.78
// bucket 9: 0.94
// sorted: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94
a = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]   # spread over [0, 1)
n = len(a)
buckets = [[] for _ in range(n)]      # n buckets, each a tenth wide
for v in a:
    buckets[int(v * n)].append(v)
out = []
for b, bucket in enumerate(buckets):
    bucket.sort()                     # each bucket is short: any sort will do
    if bucket:
        print(f"bucket {b}:", *(f"{v:.2f}" for v in bucket))
        out += bucket
print("sorted:", *(f"{v:.2f}" for v in out))

# bucket 1: 0.12 0.17
# bucket 2: 0.21 0.23 0.26
# bucket 3: 0.39
# bucket 6: 0.68
# bucket 7: 0.72 0.78
# bucket 9: 0.94
# sorted: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94
import java.util.*;

public class Main {
    public static void main(String[] args) {
        double[] a = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};   // spread over [0, 1)
        int n = a.length;
        List<List<Double>> buckets = new ArrayList<>();   // n buckets, each a tenth wide
        for (int b = 0; b < n; b++) buckets.add(new ArrayList<>());
        for (double v : a) buckets.get((int) (v * n)).add(v);
        StringBuilder sorted = new StringBuilder("sorted:");
        for (int b = 0; b < n; b++) {
            List<Double> bucket = buckets.get(b);
            Collections.sort(bucket);                  // each bucket is short: any sort will do
            if (bucket.isEmpty()) continue;
            StringBuilder line = new StringBuilder("bucket " + b + ":");
            for (double v : bucket) {
                line.append(String.format(" %.2f", v));
                sorted.append(String.format(" %.2f", v));
            }
            System.out.println(line);
        }
        System.out.println(sorted);
    }
}

// bucket 1: 0.12 0.17
// bucket 2: 0.21 0.23 0.26
// bucket 3: 0.39
// bucket 6: 0.68
// bucket 7: 0.72 0.78
// bucket 9: 0.94
// sorted: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94
const a = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68];   // spread over [0, 1)
const n = a.length;
const buckets = Array.from({ length: n }, () => []);   // n buckets, each a tenth wide
for (const v of a) buckets[Math.floor(v * n)].push(v);
const out = [];
buckets.forEach((bucket, b) => {
    bucket.sort((x, y) => x - y);         // each bucket is short: any sort will do
    if (bucket.length === 0) return;
    console.log(`bucket ${b}: ${bucket.map((v) => v.toFixed(2)).join(" ")}`);
    out.push(...bucket);
});
console.log(`sorted: ${out.map((v) => v.toFixed(2)).join(" ")}`);

// bucket 1: 0.12 0.17
// bucket 2: 0.21 0.23 0.26
// bucket 3: 0.39
// bucket 6: 0.68
// bucket 7: 0.72 0.78
// bucket 9: 0.94
// sorted: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

Ten values, ten buckets, none holding more than three. With values spread evenly, a bucket holds about one value on average and the whole sort is O(n) expected. If they bunch up, one bucket gets them all, and the sort is whatever sorts that bucket. Top K Frequent Elements (Heaps & Priority Queues) can use buckets the same way, one per frequency.

Maximum Gap

Maximum Gap asks for the largest difference between neighbours once the array is sorted, in linear time and space. Sorting first gives the answer in O(n log n); buckets give it in O(n).

Take the smallest value lo and the largest hi. n values have n − 1 gaps between neighbours, and together they span hi − lo, so the largest gap is at least the average, ⌈(hi − lo) / (n − 1)⌉. Make buckets exactly that wide. Two values in one bucket differ by less than its width, so they can't be the largest gap: the largest gap falls between buckets. Each bucket only needs its smallest and largest value, and the answer is the biggest jump from one non-empty bucket's largest to the next one's smallest:

A dashed band, buckets of width 6: 1 10 5 22 13 28: five white buckets, 1–6, 7–12, 13–18, 19–24 and 25–30, with the six values as blue dots at their places; brackets under them mark the gaps between neighbouring buckets, 5, 3, 9 and 6, the 9 from 13 to 22 in orange; each gap: the next bucket's smallest minus this one's largest. Below, a crossed card, inside a bucket: 1 and 5 share the first bucket: only 4 apart, less than its width 6; and a ticked card, between buckets: 9: 13 to 22 is the largest jump, as sorting gives: 1 5 10 13 22 28. Focal line: the largest gap is at least the width, so it spans buckets. Title: the gap falls between buckets.
#include <bits/stdc++.h>
using namespace std;

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}

int maximumGap(const vector<int>& nums) {      // the largest gap between neighbours once sorted, in O(n)
    int n = nums.size();
    if (n < 2) return 0;
    int lo = *min_element(nums.begin(), nums.end()), hi = *max_element(nums.begin(), nums.end());
    if (lo == hi) return 0;
    long long width = max(1LL, ((long long) hi - lo + n - 2) / (n - 1));   // ceil((hi - lo) / (n - 1))
    int count = (hi - lo) / width + 1;
    vector<int> small(count, INT_MAX), big(count, INT_MIN);   // each bucket's smallest and largest
    for (int v : nums) {
        int b = (v - lo) / width;
        small[b] = min(small[b], v);
        big[b] = max(big[b], v);
    }
    int best = 0, prev = big[0];               // the first bucket holds lo, so it isn't empty
    for (int b = 1; b < count; b++) {
        if (small[b] == INT_MAX) continue;     // an empty bucket: the gap spans it
        best = max(best, small[b] - prev);
        prev = big[b];
    }
    return best;
}

int main() {
    printf("%d %d %d %d\n", maximumGap({3, 6, 9, 1}), maximumGap({10}), maximumGap({1, 1, 1, 1}), maximumGap({1, 10000000}));
    vector<int> big(100000);
    for (int& v : big) v = randomBelow(1000000001);
    vector<int> sorted = big;
    sort(sorted.begin(), sorted.end());
    int scan = 0;
    for (size_t i = 1; i < sorted.size(); i++) scan = max(scan, sorted[i] - sorted[i - 1]);
    printf("100000 values: %d, and sort-then-scan gives %d\n", maximumGap(big), scan);
}

// 3 0 0 9999999
// 100000 values: 131907, and sort-then-scan gives 131907
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums


def maximum_gap(nums):                # the largest gap between neighbours once sorted, in O(n)
    n = len(nums)
    if n < 2:
        return 0
    lo, hi = min(nums), max(nums)
    if lo == hi:
        return 0
    width = max(1, -(-(hi - lo) // (n - 1)))   # ceil((hi - lo) / (n - 1))
    count = (hi - lo) // width + 1
    small, big = [None] * count, [None] * count   # each bucket's smallest and largest
    for v in nums:
        b = (v - lo) // width
        small[b] = v if small[b] is None else min(small[b], v)
        big[b] = v if big[b] is None else max(big[b], v)
    best, prev = 0, big[0]            # the first bucket holds lo, so it isn't empty
    for b in range(1, count):
        if small[b] is None:          # an empty bucket: the gap spans it
            continue
        best = max(best, small[b] - prev)
        prev = big[b]
    return best


print(maximum_gap([3, 6, 9, 1]), maximum_gap([10]), maximum_gap([1, 1, 1, 1]), maximum_gap([1, 10000000]))
big = [random_below(1000000001) for _ in range(100000)]
s = sorted(big)
scan = max(b - a for a, b in zip(s, s[1:]))
print(f"100000 values: {maximum_gap(big)}, and sort-then-scan gives {scan}")

# 3 0 0 9999999
# 100000 values: 131907, and sort-then-scan gives 131907
import java.util.*;

public class Main {
    static int seed = (int) 2463534242L;

    static int randomBelow(int bound) {          // xorshift: the same numbers in every language
        seed ^= seed << 13;
        seed ^= seed >>> 17;
        seed ^= seed << 5;
        return Integer.remainderUnsigned(seed, bound);
    }

    static int[] shuffled(int n) {               // 0 .. n-1 in a random order
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = randomBelow(i + 1), t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

    static int maximumGap(int[] nums) {        // the largest gap between neighbours once sorted, in O(n)
        int n = nums.length;
        if (n < 2) return 0;
        int lo = Arrays.stream(nums).min().getAsInt(), hi = Arrays.stream(nums).max().getAsInt();
        if (lo == hi) return 0;
        long width = Math.max(1L, ((long) hi - lo + n - 2) / (n - 1));   // ceil((hi - lo) / (n - 1))
        int count = (int) ((hi - lo) / width) + 1;
        int[] small = new int[count], big = new int[count];   // each bucket's smallest and largest
        Arrays.fill(small, Integer.MAX_VALUE);
        Arrays.fill(big, Integer.MIN_VALUE);
        for (int v : nums) {
            int b = (int) ((v - lo) / width);
            small[b] = Math.min(small[b], v);
            big[b] = Math.max(big[b], v);
        }
        int best = 0, prev = big[0];               // the first bucket holds lo, so it isn't empty
        for (int b = 1; b < count; b++) {
            if (small[b] == Integer.MAX_VALUE) continue;   // an empty bucket: the gap spans it
            best = Math.max(best, small[b] - prev);
            prev = big[b];
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maximumGap(new int[]{3, 6, 9, 1}) + " " + maximumGap(new int[]{10}) + " "
            + maximumGap(new int[]{1, 1, 1, 1}) + " " + maximumGap(new int[]{1, 10000000}));
        int[] big = new int[100000];
        for (int i = 0; i < big.length; i++) big[i] = randomBelow(1000000001);
        int[] sorted = big.clone();
        Arrays.sort(sorted);
        int scan = 0;
        for (int i = 1; i < sorted.length; i++) scan = Math.max(scan, sorted[i] - sorted[i - 1]);
        System.out.println("100000 values: " + maximumGap(big) + ", and sort-then-scan gives " + scan);
    }
}

// 3 0 0 9999999
// 100000 values: 131907, and sort-then-scan gives 131907
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

function maximumGap(nums) {               // the largest gap between neighbours once sorted, in O(n)
    const n = nums.length;
    if (n < 2) return 0;
    let lo = Infinity, hi = -Infinity;
    for (const v of nums) { lo = Math.min(lo, v); hi = Math.max(hi, v); }
    if (lo === hi) return 0;
    const width = Math.max(1, Math.ceil((hi - lo) / (n - 1)));
    const count = Math.floor((hi - lo) / width) + 1;
    const small = new Array(count).fill(Infinity), big = new Array(count).fill(-Infinity);   // each bucket's ends
    for (const v of nums) {
        const b = Math.floor((v - lo) / width);
        small[b] = Math.min(small[b], v);
        big[b] = Math.max(big[b], v);
    }
    let best = 0, prev = big[0];              // the first bucket holds lo, so it isn't empty
    for (let b = 1; b < count; b++) {
        if (small[b] === Infinity) continue;  // an empty bucket: the gap spans it
        best = Math.max(best, small[b] - prev);
        prev = big[b];
    }
    return best;
}

console.log(maximumGap([3, 6, 9, 1]), maximumGap([10]), maximumGap([1, 1, 1, 1]), maximumGap([1, 10000000]));
const big = Array.from({ length: 100000 }, () => randomBelow(1000000001));
const sorted = big.slice().sort((x, y) => x - y);
let scan = 0;
for (let i = 1; i < sorted.length; i++) scan = Math.max(scan, sorted[i] - sorted[i - 1]);
console.log(`100000 values: ${maximumGap(big)}, and sort-then-scan gives ${scan}`);

// 3 0 0 9999999
// 100000 values: 131907, and sort-then-scan gives 131907

[3, 6, 9, 1] gives 3, a single value or all equal give 0, and 100,000 values up to 10⁹ gave 131,907, the same as sorting and scanning. C++ and Java compute the width in 64 bits: with values up to 10⁹, hi − lo + n − 2 fits in an int, but with values up to 2³¹ − 1 it wouldn't.

Gap Between Buckets. Drop each value into its bucket, then pick the largest gap between neighbouring non-empty buckets. Try the array with empty buckets in the middle, and the one where every value is equal.

Gap Between Buckets: place the values, then pick the largest gap between buckets

Spotting it

The clues: keys in a small known range (ages, scores, letters, digits), keys of a fixed length (dates, IDs, equal-length strings), values spread evenly over a range, or "in linear time" for a problem that sounds like sorting. Near misses:

  • Keys with no small range and no fixed length, compared any way the problem likes: a comparison sort (Merge Sort and Counting Inversions, Quick Sort and Partitioning).
  • The k most frequent values: buckets by frequency, or a heap (Top K and the Kth Element).
  • Three known values: one three-way partition (Sort Colors), no counts needed.

Mistakes that cost an interview

Placing from the left with the end positions. The counts say where each key's run ends; filled from its end while walking from the left, equal keys come out reversed, and radix sort's passes no longer agree:

def by_digit(a, place):                # the radix pass, but placed from the left using where each digit ends
    count = [0] * 10
    for v in a:
        count[v // place % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]
    out = [0] * len(a)
    for v in a:                       # left to right, filling each digit's slots from its end
        count[v // place % 10] -= 1
        out[count[v // place % 10]] = v
    return out


a = [170, 45, 75, 90, 802, 24, 2, 66]
for place in (1, 10, 100):
    a = by_digit(a, place)
print(*a)

# 90 75 66 45 24 2 170 802

That's 90 75 66 45 24 2 170 802, not sorted. Walk from the right with the end positions, or from the left with the start positions.

Counting sort on a huge range. Keys up to 10⁹ need a billion counters, 4 GB; with a few thousand values, sort them, or compress the keys to ranks first (Introduction to Sorting showed the ranks).

A bucket width of 0 in Maximum Gap. All-equal values make (hi − lo) // (n − 1) zero:

def maximum_gap(nums):                # buckets of width (hi - lo) // (n - 1), with no guard
    lo, hi, n = min(nums), max(nums), len(nums)
    width = (hi - lo) // (n - 1)
    seen = {}
    for v in nums:
        b = (v - lo) // width
        seen[b] = seen.get(b, []) + [v]
    return width


try:
    maximum_gap([7, 7, 7])
except ZeroDivisionError as e:
    print("ZeroDivisionError:", e)

# ZeroDivisionError: integer division or modulo by zero

Return 0 when hi equals lo, and round the width up to at least 1.

Skipping the empty buckets wrongly. The gap after an empty bucket runs from the last non-empty bucket's largest value, not from the empty one, which is why the code keeps prev.

Check yourself

Quiz

1 / 6

Multiple choice

At least how many comparisons does some order of 8 values need, for any comparison sort?

Practice

In this section:

  • Maximum Gap: buckets the width of the average gap; the answer falls between them.

Also practised elsewhere: Sort Characters By Frequency (Strings) counts letters, and Sort Colors (Two Pointers) sorts three values in one pass. Sorting Quiz, at the end of this section, mixes all four lessons.