LeetCode 1356 - Sort Integers by The Number of 1 Bits

LeetCode Problem 1356

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation, Sorting, Counting

Solution

Problem Understanding

The problem asks us to sort an integer array arr based on the number of 1 bits in the binary representation of each element. This means that we are not sorting by the integer value itself but by the count of 1s in its binary form. If two numbers have the same number of 1s, we then sort them by their numeric value in ascending order.

The input is a list of integers, with each integer ranging from 0 to 10,000, and the list itself has up to 500 elements. The output is a new array with the same integers sorted according to the described rules.

Key constraints are small enough that an efficient sorting algorithm with a custom comparator will perform well. Edge cases that may require careful handling include arrays with all elements having the same number of 1s, arrays containing zero, and arrays with duplicates.

Approaches

The brute-force approach would involve first calculating the number of 1 bits for each element, storing this information, and then performing a sort based on this count, followed by a numeric comparison for tie-breaking. While straightforward, this can be inefficient if not implemented carefully.

The optimal solution leverages Python or Go's ability to sort with a custom key or comparator. The key insight is that for each integer, the sorting criterion can be represented as a tuple (number_of_1_bits, integer_value). Sorting an array of such tuples ensures the correct ordering because the sort is lexicographical, first by the number of 1s, then by the integer value. This approach is clean, efficient, and easy to implement.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n + n * k)	O(n)	Compute 1 bits count and sort using extra storage for counts; k is max bits (≤14)
Optimal	O(n log n)	O(n)	Sort using a tuple key (bit_count, value); no separate data structure required

Algorithm Walkthrough

1. Iterate over each integer in the array and calculate its number of 1 bits. This can be done using a built-in function like bin(x).count('1') in Python or bits.OnesCount(uint(x)) in Go.
2. Pair each integer with its corresponding bit count, effectively creating a tuple (bit_count, integer).
3. Sort the array of tuples. The sort will prioritize the first element of the tuple (bit count) and use the second element (integer value) for tie-breaking.
4. Extract the integers from the sorted tuples to obtain the final sorted array.

Why it works: Sorting based on a tuple of (bit_count, integer) guarantees that all numbers are ordered first by their binary 1s count and then numerically for equal bit counts. The tuple sorting ensures correctness because lexicographical comparison handles the tie-breaking naturally.

Python Solution

from typing import List

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        return sorted(arr, key=lambda x: (bin(x).count('1'), x))

This implementation uses Python’s sorted() function with a lambda as the key. The lambda constructs a tuple (bin(x).count('1'), x). Here bin(x).count('1') calculates the number of 1s in the binary representation. Python sorts tuples lexicographically, so this automatically handles the tie-breaking by the integer value. The code is concise, readable, and runs efficiently for the given constraints.

Go Solution

import (
    "sort"
    "math/bits"
)

func sortByBits(arr []int) []int {
    sort.Slice(arr, func(i, j int) bool {
        countI := bits.OnesCount(uint(arr[i]))
        countJ := bits.OnesCount(uint(arr[j]))
        if countI == countJ {
            return arr[i] < arr[j]
        }
        return countI < countJ
    })
    return arr
}

In Go, we use sort.Slice with a custom comparator function. The function calculates the number of 1s using bits.OnesCount, which is a highly efficient standard library method. If two elements have the same bit count, the comparator returns the smaller integer first, ensuring the correct tie-breaking order.

Worked Examples

Example 1

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

Number	Binary	Bit Count
0	0	0
1	1	1
2	10	1
3	11	2
4	100	1
5	101	2
6	110	2
7	111	3
8	1000	1

Sort by bit count, then by value: [0,1,2,4,8,3,5,6,7]

Example 2

Input: [1024,512,256,128,64,32,16,8,4,2,1]

All have 1 bit. Sort numerically: [1,2,4,8,16,32,64,128,256,512,1024]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting n elements dominates; counting bits is O(k) per element but k ≤ 14, so treated as constant
Space	O(n)	Sorting creates a copy in Python, Go sorts in-place

The algorithm is efficient because counting bits is negligible and sorting handles tie-breaking automatically.

Test Cases

# Provided examples
assert Solution().sortByBits([0,1,2,3,4,5,6,7,8]) == [0,1,2,4,8,3,5,6,7]  # multiple bit counts
assert Solution().sortByBits([1024,512,256,128,64,32,16,8,4,2,1]) == [1,2,4,8,16,32,64,128,256,512,1024]  # all same bit count

# Edge cases
assert Solution().sortByBits([0]) == [0]  # single element
assert Solution().sortByBits([7,7,7,7]) == [7,7,7,7]  # duplicates
assert Solution().sortByBits([0, 1, 3, 7]) == [0, 1, 3, 7]  # powers of 2 included
assert Solution().sortByBits([5,3,10,15]) == [3,5,10,15]  # mixed bit counts

Test	Why
[0,1,2,3,4,5,6,7,8]	Tests multiple bit counts and tie-breaking
[1024,512,...,1]	Tests uniform bit count, numeric sort
[0]	Tests smallest input
[7,7,7,7]	Tests handling duplicates
[5,3,10,15]	Tests mixed numbers with different bit counts

Edge Cases

1. Single element array: If the array contains only one number, the function must return it unchanged. This tests that the algorithm handles minimal input and does not assume multiple elements.
2. All elements have the same number of 1s: Arrays like [2,4,8,16] should be sorted numerically. This edge case ensures tie-breaking logic is correct.
3. Array contains zero: Zero has zero 1s. It must appear first if sorting correctly, which could trip up algorithms that assume all numbers are positive and non-zero.

This completes a comprehensive reference solution for LeetCode 1356.