Let’s dive into explaining the solution for LeetCode Problem 1356: Sort Integers by The Number of 1 Bits, covering the problem requirements, the provided code’s functionality, a complexity analysis, and verifying the solution’s correctness. The code you shared uses a Comparator-based approach to sort an array of integers based on their Hamming weight (number of 1s in their binary representation) and then by their numerical value for ties. I’ll break it down step by step, provide the complexity analysis, and confirm the complete solution.

Problem Explanation: LeetCode 1356

Problem Statement:

Input: An array arr of integers.
Output: The array sorted such that:
- Primary key: Number of 1s in the binary representation of each integer (Hamming weight).
- Secondary key: The integer’s value (for numbers with the same number of 1s).
Constraints:
- 1 <= arr.length <= 500
- 0 <= arr[i] <= 10^4
Example:
- Input: arr = [0,1,2,3,4,5,6,7,8]
- Output: [0,1,2,4,8,3,5,6,7]
- Explanation:
  - Bit counts: 0:0, 1:1, 2:1, 3:2, 4:1, 5:2, 6:2, 7:3, 8:1
  - Group by bit count: [0], [1,2,4,8], [3,5,6], [7]
  - Sort within each group by value: [0], [1,2,4,8], [3,5,6], [7]
  - Final array: [0,1,2,4,8,3,5,6,7]

The goal is to sort arr by the number of 1s in each integer’s binary form, and for equal bit counts, sort by the integer itself in ascending order.

Code Explanation

The provided solution converts the input int[] to an Integer[], sorts it using a custom Comparator, and converts it back to int[]. Here’s the code with a detailed breakdown:

import java.util.Arrays;

class Solution {
    public int[] sortByBits(int[] arr) {
        // Convert int[] to Integer[] for sorting with Comparator
        Integer[] boxed = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            boxed[i] = arr[i];
        }

        // Sort using Comparator
        Arrays.sort(boxed, (a, b) -> {
            int countA = Integer.bitCount(a);
            int countB = Integer.bitCount(b);
            if (countA != countB) {
                return countA - countB; // Sort by bit count
            }
            return a - b; // If bit counts equal, sort by value
        });

        // Convert Integer[] back to int[]
        int[] result = new int[boxed.length];
        for (int i = 0; i < boxed.length; i++) {
            result[i] = boxed[i];
        }

        return result;
    }
}

Step-by-Step Breakdown

Import Statement:
- import java.util.Arrays; provides access to Arrays.sort and other utility methods.
Convert int[] to Integer[]:
```
Integer[] boxed = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) {
    boxed[i] = arr[i];
}
```
- Creates an Integer[] array (boxed) of the same length as arr.
- Copies each element from arr to boxed, autoboxing int to Integer.
- Why? Java’s Arrays.sort(T[], Comparator) works with object arrays (T[] where T extends Object), not primitive arrays like int[]. Converting to Integer[] allows us to use a custom Comparator.
Sort with Custom Comparator:
```
Arrays.sort(boxed, (a, b) -> {
    int countA = Integer.bitCount(a);
    int countB = Integer.bitCount(b);
    if (countA != countB) {
        return countA - countB; // Sort by bit count
    }
    return a - b; // If bit counts equal, sort by value
});
```
- Uses Arrays.sort with a lambda expression defining a Comparator<Integer>.
- For two integers a and b:
  - Compute countA and countB using Integer.bitCount, which returns the number of 1s in the binary representation.
  - If countA != countB, return countA - countB to sort by bit count in ascending order (smaller bit count comes first).
  - If countA == countB, return a - b to sort by the integer value in ascending order (tiebreaker).
- The lambda returns:
  - Negative value if a should come before b.
  - Positive value if b should come before a.
  - Zero if equal (though stable sorting preserves order).
Convert Integer[] back to int[]:
```
int[] result = new int[boxed.length];
for (int i = 0; i < boxed.length; i++) {
    result[i] = boxed[i];
}
```
- Creates a new int[] array (result) to match the method’s return type.
- Copies each element from boxed to result, unboxing Integer to int.
- Necessary because the problem requires an int[] return type.
Return:
```
return result;
```
- Returns the sorted int[] array.

Example Walkthrough

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

Step 1: Convert to Integer[]:
- boxed = [0,1,2,3,4,5,6,7,8]
Step 2: Sort:
- Bit counts: 0:0, 1:1, 2:1, 3:2, 4:1, 5:2, 6:2, 7:3, 8:1
- Comparator logic:
  - Compare bit counts first, then values.
  - Group by bit count: [0], [1,2,4,8], [3,5,6], [7].
  - Within groups, sort by value: [0], [1,2,4,8], [3,5,6], [7].
- Sorted boxed: [0,1,2,4,8,3,5,6,7]
Step 3: Convert back:
- result = [0,1,2,4,8,3,5,6,7]
Output: [0,1,2,4,8,3,5,6,7]

Correctness

The solution correctly:

Sorts by bit count (ascending) using Integer.bitCount.
Breaks ties by sorting numbers with equal bit counts in ascending order.
Handles all constraints:
- Array length 1 <= arr.length <= 500.
- Values 0 <= arr[i] <= 10^4, so Integer.bitCount (max 14 for 10^4) works safely.
- Edge cases (e.g., single element, all same bit count) are handled by the stable sorting and tiebreaker logic.

Complexity Analysis

Let’s analyze the time and space complexity of the solution.

Time Complexity

Conversion to Integer[]:
- Loop over arr (length n): O(n).
Sorting:
- Arrays.sort uses TimSort, which has a time complexity of O(n log n) for an array of length n.
- Inside the comparator:
  - Integer.bitCount is O(1) (constant-time operation for 32-bit integers, using hardware bit-counting or optimized algorithms like popcount).
  - Comparator is called O(log n) times per element during sorting, but O(1) per comparison.
  - Total sorting cost: O(n log n).
Conversion back to int[]:
- Loop over boxed (length n): O(n).
Total Time Complexity:
- O(n) + O(n log n) + O(n) = O(n log n).
- The sorting step dominates.

Space Complexity

Arrays:
- boxed array: O(n) (stores n Integer objects).
- result array: O(n) (stores n int values).
Sorting:
- TimSort uses O(log n) auxiliary space for the call stack (merge sort component).
Total Space Complexity:
- O(n) for the arrays, plus O(log n) for sorting, which simplifies to O(n).

Alternative Solution (Magic Number Approach)

For comparison, another solution (previously discussed) uses a "magic number" to encode bit counts into the integers themselves, avoiding the need for a Comparator. Here’s a brief overview to contrast:

class Solution {
    public int[] sortByBits(int[] arr) {
        final int MAGIC_NUMBER = 10001; // Larger than max arr[i] (10^4)
        for (int i = 0; i < arr.length; i++) {
            arr[i] += Integer.bitCount(arr[i]) * MAGIC_NUMBER;
        }
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] %= MAGIC_NUMBER;
        }
        return arr;
    }
}

How it works: Adds bitCount * MAGIC_NUMBER to each element, sorts, then uses modulo to restore original values.
Time Complexity: O(n log n) (sorting dominates; Integer.bitCount is O(1)).
Space Complexity: O(1) auxiliary space (in-place modification, excluding TimSort’s O(log n) stack space).
Trade-off: More space-efficient but less intuitive and modifies the input array.

The provided Comparator solution is clearer and doesn’t modify the input array directly, but uses O(n) extra space.

Complete Solution

The provided code is correct and matches the problem requirements. For completeness, here it is again with inline comments:

import java.util.Arrays;

class Solution {
    public int[] sortByBits(int[] arr) {
        // Convert int[] to Integer[] to use Comparator
        Integer[] boxed = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            boxed[i] = arr[i]; // Autobox int to Integer
        }

        // Sort by bit count, then by value
        Arrays.sort(boxed, (a, b) -> {
            int countA = Integer.bitCount(a); // Count 1s in a
            int countB = Integer.bitCount(b); // Count 1s in b
            if (countA != countB) {
                return countA - countB; // Ascending by bit count
            }
            return a - b; // Ascending by value for equal bit counts
        });

        // Convert Integer[] back to int[]
        int[] result = new int[boxed.length];
        for (int i = 0; i < boxed.length; i++) {
            result[i] = boxed[i]; // Unbox Integer to int
        }

        return result;
    }
}

Summary

Problem: Sort an array by the number of 1s in each integer’s binary representation, with numerical value as a tiebreaker.
Solution: Converts int[] to Integer[], sorts using a Comparator based on Integer.bitCount and value, then converts back to int[].
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for the boxed and result arrays.
Correctness: Handles all cases, including edge cases (empty array, single element, equal bit counts).
The code is robust, readable, and meets all problem constraints efficiently.

LeetCode Problem 1356 Sort Integers by The Number of 1 Bits (Easy, Java, O(nlogn))

Table of contents