Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The requested ordering has two keys: set-bit count first, numeric value second. Sorting numerically first and then stably sorting by bit count preserves ascending numeric order within every equal-count group.

Approach

Sort the array by value. Compute set-bit counts by repeatedly clearing the lowest set bit; Python subtracts x & -x, and zero naturally has count zero. Perform a stable sort using those counts as the primary key, then return the array. Stability is what makes the first numeric sort remain effective for ties, including repeated values. The implementations reuse calculated counts rather than recounting all bits on every comparison.

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        def bit_count(x):
            b = 0

            while x:
                # b += x % 2 == 1
                # x //= 2
                x -= x & -x
                b += 1

            return b

        arr.sort()
        arr.sort(key = lambda x: bit_count(x))
        return arr

Complexity analysis

Let n be the array length and B the maximum bit-count work per value. Both displayed implementations evaluate bit counts once per value (or distinct value) and perform stable sorting, using O(n log n + nB) time and O(n) auxiliary sort/key-storage space.