Sort array according to count of set bits

The problem, simply

Every number can be written in binary, with only 0s and 1s. The 1s are called set bits. For example 13 is 1101, which has 3 set bits.

You get an array of non-negative numbers. Sort it so that numbers with more set bits come first. When two numbers have the same count, keep them in the order they had in the input. A sort that keeps ties in order is called stable.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use the library sort with a comparator that compares set bit counts, biggest first. Java's sort for objects is stable, so ties keep their order.

1. Count set bits with a classic trick: x & (x - 1) turns off the lowest 1. Repeat until x is 0 and count the steps.
2. Sort with the comparator count(b) - count(a).

class Solution {
    int countBits(int x) {
        int c = 0;
        while (x != 0) {
            x &= x - 1;          // turn off the lowest light
            c++;
        }
        return c;
    }

    public int[] sortBySetBits(int[] arr) {
        Integer[] boxed = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) boxed[i] = arr[i];
        // object sort in Java is stable, so ties keep their input order
        Arrays.sort(boxed, (a, b) -> Integer.compare(countBits(b), countBits(a)));
        int[] out = new int[arr.length];
        for (int i = 0; i < arr.length; i++) out[i] = boxed[i];
        return out;
    }
}

How long it takes: the sort makes O(n log n) comparisons, and each one counts bits in at most 32 steps, so O(n log n). Extra room: the boxed copy and the merge buffer, O(n).

Way 2: the clever way

A count of set bits is a small number, from 0 to 32. So use 33 buckets instead of comparing.

1. Make 33 empty lists, one per count.
2. Walk the input from left to right. Put each number at the end of the list for its count.
3. Read the lists from 32 down to 0 and write the numbers out.

Because numbers enter each bucket in input order and leave in the same order, ties stay in order for free.

class Solution {
    public int[] sortBySetBits(int[] arr) {
        List<List<Integer>> buckets = new ArrayList<>();
        for (int c = 0; c <= 32; c++) buckets.add(new ArrayList<>());
        for (int x : arr) {
            buckets.get(Integer.bitCount(x)).add(x);   // join the back of its bucket
        }
        int[] out = new int[arr.length];
        int k = 0;
        for (int c = 32; c >= 0; c--) {                 // most lights first
            for (int x : buckets.get(c)) out[k++] = x;
        }
        return out;
    }
}

How long it takes: one pass to fill the buckets and one pass to read them, plus 33 bucket checks, O(n). Extra room: the buckets hold every number once, O(n).

Watch out for

• Getting the order backwards. The problem asks for most set bits first, so compare b before a, or read buckets from 32 down.
• Negative numbers in Java have 32 bit two's complement form, so -1 has 32 set bits. The problem says non-negative, but ask if negatives can appear.
• Recounting bits inside every comparison is wasteful. You can count once per number and sort pairs (count, index).

What interviewers ask next

• Sort by set bits ascending, and break ties by value (LeetCode 1356). Change the comparator: compare counts, then values.
• How does Integer.bitCount work so fast? It adds bits in pairs, then nibbles, then bytes, using masks like 0x55555555. Or the CPU has a popcount instruction.
• Count set bits for every number from 0 to n in O(n). Use bits[i] = bits[i >> 1] + (i & 1).
• When is bucket sort better than comparison sort in general? When the key has a small range, like grades, ages, or bit counts. Then it is linear.

Remember this

Grown-up words: the lights are bits, lights that are on are set bits and counting them is popcount, the buckets are counting sort (bucket sort by key), and keeping ties in order is a stable sort.