Is Sort Integers by The Number of 1 Bits easy or hard?

The problem is classified as Easy because the core idea is straightforward once you recognize that sorting should use the bit count as a key. Most of the work is using a popcount function and defining the correct comparator. It mainly checks familiarity with bit operations and custom sorting.

Sort Integers by The Number of 1 Bits Python/Java solution

In Python, sort the list with key=lambda x: (bin(x).count('1'), x). In Java, use Arrays.sort with a comparator that compares Integer.bitCount(a) and Integer.bitCount(b), then compares the numbers if counts match. Both implementations run in O(n log n) time.

How to solve Sort Integers by The Number of 1 Bits in O(n)?

Pure O(n) ordering is generally not used because comparison-based sorting dominates the runtime. A near-linear strategy can group numbers by their bit counts using buckets and then sort each bucket by value. Even then, ordering within buckets typically requires sorting, so the practical complexity remains around O(n log n).

What is the best approach for Sort Integers by The Number of 1 Bits?

The most practical approach sorts the array using a custom key that returns (bitCount(x), x). The bit count determines the primary ordering, and the integer value breaks ties. Built-in functions like Python's bin(x).count('1') or Java's Integer.bitCount make this straightforward. The overall complexity is O(n log n) due to sorting.

Is Sort Integers by The Number of 1 Bits asked at Google/Amazon/Meta?

Bit manipulation and custom sorting problems like this appear in interviews at companies such as Amazon and Google. The problem tests understanding of popcount operations, comparator design, and stable ordering rules. Interviewers often expect candidates to quickly identify the (bitCount, value) sorting key.

What data structure is used in Sort Integers by The Number of 1 Bits?

The main data structure is an array that gets reordered using a sorting algorithm. Some implementations also use auxiliary pairs or tuples like (bitCount, value) to simplify comparisons. The key operation relies on bit manipulation to compute the number of set bits in each integer.

What is the time complexity of Sort Integers by The Number of 1 Bits?

The dominant cost is sorting the array, which takes O(n log n) time. Computing the number of set bits for each element is O(B) where B is the bit length of the integer (typically up to 32), making it effectively constant. Overall complexity remains O(n log n) with O(1) to O(n) auxiliary space depending on the implementation.

Description Hints 2 Solution Video 21:46

1356. Sort Integers by The Number of 1 Bits

Easy82.3% acceptance4 companies

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the array after sorting it.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Constraints: