Problem Description

You are given an integer array arr. Your task is to sort this array based on two criteria:

1. Primary criterion: Sort the integers in ascending order by the number of 1s in their binary representation
2. Secondary criterion: If two or more integers have the same number of 1s in their binary representation, sort them in ascending order by their numerical value

Return the sorted array.

For example, if we have numbers like 2 (binary: 10, one 1), 3 (binary: 11, two 1s), and 4 (binary: 100, one 1), we would first group them by the count of 1s:

• Numbers with one 1: 2 and 4
• Numbers with two 1s: 3

Within each group, we sort by value. So the final order would be [2, 4, 3] because:

• 2 comes first (one 1, smaller value)
• 4 comes second (one 1, larger value than 2)
• 3 comes last (two 1s)

The solution uses Python's sorted() function with a custom key that returns a tuple (x.bit_count(), x). The bit_count() method counts the number of 1s in the binary representation, and by including x itself as the second element of the tuple, Python automatically handles the secondary sorting by numerical value when the bit counts are equal.

Intuition

When we need to sort elements based on multiple criteria, we can leverage Python's built-in sorting capabilities which naturally handle tuple comparisons. The key insight is that Python compares tuples element by element from left to right - it first compares the first elements, and only if they're equal does it move on to compare the second elements.

This problem asks us to sort by two criteria: the count of 1s in binary representation (primary) and the numerical value itself (secondary). We can represent each number as a tuple where:

• The first element is the bit count (number of 1s)
• The second element is the number itself

For example, the number 5 (binary: 101) would be represented as (2, 5) because it has two 1s. The number 8 (binary: 1000) would be (1, 8) with one 1.

When Python sorts these tuples, it naturally achieves what we want:

• (1, 8) comes before (2, 5) because 1 < 2 (fewer bits)
• (2, 3) comes before (2, 5) because when the first elements are equal (2 == 2), it compares the second elements (3 < 5)

The elegant part of this solution is using x.bit_count() which directly gives us the count of 1s in the binary representation, eliminating the need to manually convert to binary and count. By creating the key as (x.bit_count(), x), we let Python's natural tuple sorting behavior handle all the complexity for us in a single line of code.

Learn more about Sorting patterns.

Solution Approach

The solution uses Python's custom sorting capability to solve this problem efficiently. Here's how the implementation works:

Algorithm: Custom Sorting with Lambda Function

The core of the solution is the single line:

return sorted(arr, key=lambda x: (x.bit_count(), x))

Let's break down each component:

1. sorted() function: Python's built-in sorting function that creates a new sorted list from the input array. It accepts a key parameter that determines how elements are compared.

2. Lambda function as key: lambda x: (x.bit_count(), x)

   • This creates an anonymous function that takes each element x from the array
   • Returns a tuple with two values for sorting comparison

3. The sorting tuple (x.bit_count(), x):

   • First element: x.bit_count() - counts the number of 1s in the binary representation of x
   • Second element: x - the original number itself

How the sorting works:

When Python sorts using this key function, for each number in the array:

1. It applies the lambda function to get a tuple
2. Sorts all tuples lexicographically (comparing first elements, then second if first are equal)
3. Returns the original numbers in the sorted order

Example walkthrough:

For array [0, 1, 2, 3, 4, 5, 6, 7, 8]:

• 0 → (0, 0) (binary: 0, zero 1s)
• 1 → (1, 1) (binary: 1, one 1)
• 2 → (1, 2) (binary: 10, one 1)
• 3 → (2, 3) (binary: 11, two 1s)
• 4 → (1, 4) (binary: 100, one 1)
• And so on...

After sorting these tuples, we get the order: [0, 1, 2, 4, 8, 3, 5, 6, 7]

Time Complexity: O(n log n) due to the sorting operation Space Complexity: O(n) for the sorted array creation

Example Walkthrough

Let's walk through a small example with the array [7, 2, 3, 9, 4].

Step 1: Convert each number to its sorting key (bit_count, value)

For each number, we calculate the bit count and create a tuple:

• 7 → binary: 111 → has 3 ones → key: (3, 7)
• 2 → binary: 10 → has 1 one → key: (1, 2)
• 3 → binary: 11 → has 2 ones → key: (2, 3)
• 9 → binary: 1001 → has 2 ones → key: (2, 9)
• 4 → binary: 100 → has 1 one → key: (1, 4)

Step 2: Sort by these tuple keys

Now we sort these tuples lexicographically:

• (1, 2) - 1 bit set, value 2
• (1, 4) - 1 bit set, value 4
• (2, 3) - 2 bits set, value 3
• (2, 9) - 2 bits set, value 9
• (3, 7) - 3 bits set, value 7

Notice how:

• Numbers with 1 bit come first: 2 and 4 (sorted by value: 2 < 4)
• Numbers with 2 bits come next: 3 and 9 (sorted by value: 3 < 9)
• Numbers with 3 bits come last: only 7

Step 3: Extract the sorted numbers

The final sorted array is: [2, 4, 3, 9, 7]

This demonstrates both sorting criteria:

1. Primary: Numbers are grouped by bit count (1-bit group, then 2-bit group, then 3-bit group)
2. Secondary: Within each group, numbers are in ascending order (2 before 4, and 3 before 9)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

The time complexity is dominated by the sorted() function, which uses Timsort algorithm in Python. The sorting operation has a time complexity of O(n log n) where n is the length of the input array arr.

For each element during sorting, we need to:

• Calculate x.bit_count(): This operation takes O(log x) time in the worst case, where x is the value of the element. However, since we're dealing with fixed-size integers (typically 32-bit or 64-bit), this can be considered O(1).
• Create the tuple (x.bit_count(), x) for comparison: O(1)

Since the bit counting operation is O(1) for fixed-size integers and is performed for each comparison during sorting, the overall time complexity remains O(n log n).

Space Complexity: O(n)

The space complexity consists of:

• The sorted() function creates a new list containing all n elements: O(n)
• The sorting algorithm (Timsort) uses additional space for its operations: O(n) in the worst case
• The lambda function and temporary tuples created during comparisons use O(1) space

Therefore, the total space complexity is O(n) where n is the length of the array arr.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Manual Bit Counting Instead of Built-in Methods

A common pitfall is implementing custom bit counting logic when Python provides efficient built-in methods. Developers might write:

# Inefficient manual approach
def count_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

return sorted(arr, key=lambda x: (count_bits(x), x))

Why it's problematic:

• More code to maintain and debug
• Potentially slower than optimized built-in methods
• Higher chance of bugs (e.g., not handling negative numbers correctly)

Solution: Use bit_count() for Python 3.10+ or bin(x).count('1') for earlier versions:

# Python 3.10+
return sorted(arr, key=lambda x: (x.bit_count(), x))

# Python < 3.10
return sorted(arr, key=lambda x: (bin(x).count('1'), x))

2. Forgetting to Handle Negative Numbers

The problem statement doesn't explicitly mention negative numbers, but if they're present in the input, the behavior might be unexpected:

# Negative numbers have different binary representations
-1  # In two's complement: all bits are 1
-2  # Binary representation depends on system architecture

Solution: Either validate input or handle negative numbers explicitly:

def sortByBits(self, arr: List[int]) -> List[int]:
    # Option 1: Filter out negatives if not allowed
    if any(x < 0 for x in arr):
        raise ValueError("Negative numbers not supported")
  
    # Option 2: Handle negatives by using absolute value for bit counting
    return sorted(arr, key=lambda x: (bin(abs(x)).count('1'), x))

3. Modifying the Original Array Instead of Returning a New One

Some developers might use arr.sort() instead of sorted(arr):

# This modifies the original array
arr.sort(key=lambda x: (x.bit_count(), x))
return arr  # Original array is modified

Why it matters:

• The problem asks to "return the sorted array" which typically implies creating a new array
• Modifying the input can cause unexpected side effects if the caller expects the original array to remain unchanged

Solution: Use sorted() to create a new sorted list:

return sorted(arr, key=lambda x: (x.bit_count(), x))

4. Not Considering Edge Cases

Failing to handle edge cases like empty arrays or single-element arrays:

# Potential issues with edge cases
if not arr:  # Empty array
    return []
if len(arr) == 1:  # Single element
    return arr

Solution: The current implementation with sorted() naturally handles these cases, but it's good practice to document expected behavior:

def sortByBits(self, arr: List[int]) -> List[int]:
    """
    Sort array by bit count then value.
    Handles empty arrays and single elements correctly.
    """
    # sorted() handles empty and single-element arrays correctly
    return sorted(arr, key=lambda x: (x.bit_count(), x))

5. Performance Optimization Misconception

Trying to optimize by caching bit counts when it's unnecessary:

# Over-engineered solution
bit_cache = {}
for num in arr:
    bit_cache[num] = num.bit_count()

return sorted(arr, key=lambda x: (bit_cache[x], x))

Why it's unnecessary:

• For typical array sizes, the overhead of creating and accessing the cache might not provide benefits
• bit_count() is already highly optimized
• Adds complexity without significant performance gain

Solution: Keep it simple unless profiling shows a real bottleneck:

return sorted(arr, key=lambda x: (x.bit_count(), x))