What is the time and space complexity of Sort Integers by 1 Bits?

Time complexity: O(n log n). Space complexity: O(n).

Sort Integers by 1 Bits

Easy

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Sort Integers by 1 Bits

Approach

Compute the popcount (number of set bits) for each integer using Brian Kernighan's algorithm. Sort the array with a custom comparator that orders by ascending popcount first, then by ascending numeric value for ties.

Complexity Analysis

Time: O(n log n)
Space: O(n)

Pattern

Bit Counting

Why It Works

The comparator encodes a two-level sort key: primary key is the number of 1-bits, secondary key is the integer value itself, producing a stable ordering by bit density.

Updated Feb 2026