Sort Integers by Binary Reflection solution and explanation
4 more videos on this problem
Leetcode | 3769 Sort Integers by Binary Reflection | Java | Sorting | Weekly Contest - 479Cakot Coding · 10:56 · 292 views
Sort Integer by Binary Reflection 🔥 Leetcode 3769 | Weekly Contest 479 Q1 | Easy Sorting + Binary Study Placement · 8:47 · 281 views
LeetCode 3769 | Sort Integers by Binary Reflection | Step-by-Step with Java CodeCode Kage · 10:26 · 142 views
3769. Sort Integers by Binary Reflection (Leetcode Easy)Programming Live with Larry · 3:36 · 103 views
Sort Integers by Binary Reflection | LeetCode 3769 | SortingcodeTips · 6:00 · 51 views
The problem
You are given an integer array nums.
The binary reflection of a positive integer is defined as the number obtained by reversing the order of its binary digits (ignoring any leading zeros) and interpreting the resulting binary number as a decimal.
Sort the array in ascending order based on the binary reflection of each element. If two different numbers have the same binary reflection, the smaller original number should appear first.
Return the resulting sorted array.
Example 1:
Input: nums = [4,5,4]
Output: [4,4,5]
Explanation:
Binary reflections are:
- 4 -> (binary)
100-> (reversed)001-> 1 - 5 -> (binary)
101-> (reversed)101-> 5 - 4 -> (binary)
100-> (reversed)001-> 1
[4, 4, 5].Example 2:
Input: nums = [3,6,5,8]
Output: [8,3,6,5]
Explanation:
Binary reflections are:
- 3 -> (binary)
11-> (reversed)11-> 3 - 6 -> (binary)
110-> (reversed)011-> 3 - 5 -> (binary)
101-> (reversed)101-> 5 - 8 -> (binary)
1000-> (reversed)0001-> 1
[8, 3, 6, 5].Note that 3 and 6 have the same reflection, so we arrange them in increasing order of original value.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 109
Approach overview
Problem Overview: You are given a list of integers and need to sort them based on their binary reflection. For each number, convert it to binary, reverse the bit sequence, interpret the reversed bits as a new integer, and sort the array according to this reflected value.
Approach 1: Brute Force Reflection During Comparison (O(n log n * b) time, O(1) extra space)
The most direct solution uses a custom comparator during sorting. Every time two numbers are compared, convert each integer to its binary form, reverse the bit string, convert it back to a decimal value, and compare those reflected values. The sorting algorithm repeatedly performs these conversions, which adds overhead proportional to the number of bits b. This approach works but is inefficient because the same reflection may be recomputed many times during the sort.
Approach 2: Custom Sorting with Precomputed Reflection Keys (O(n log n) time, O(n) space)
A more efficient method computes the binary reflection for each integer once and uses it as a sorting key. Iterate through the array, convert each number to binary, reverse the bits, and store the resulting integer. Then apply a standard sort where the key is this precomputed reflection value. Most languages support this pattern using a key function or custom comparator. Because each reflection is calculated once, the overall complexity becomes O(n log n) for sorting plus O(n * b) preprocessing.
The core operation is the bit reflection step. You can perform it by converting the number to a binary string and reversing it, or by repeatedly extracting the least significant bit and building the reversed value using bit operations. The bitwise method avoids string allocations and can be slightly faster, though both approaches are acceptable for an easy-level problem.
This problem mainly tests your understanding of array manipulation and custom comparators in sorting. The key insight is that the original value does not determine order directly; the order is based on a transformed representation of each element.
Recommended for interviews: Use the precomputed reflection key approach with custom sorting. Start by explaining the brute force comparator to demonstrate the core idea, then optimize by computing reflections once and sorting with a key function. Interviewers expect you to recognize unnecessary repeated work inside comparators and move that logic outside the sort.
Solution
We define a function f(x) to calculate the binary reflection value of integer x. Specifically, we continuously extract the lowest bit of x and add it to the end of the result y until x becomes 0.
Then, we sort the array nums with the sorting key being the tuple (f(x), x) of each element's binary reflection value and original value. This ensures that when two elements have the same binary reflection value, the smaller original value will be placed first.
Finally, we return the sorted array.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array nums.
class Solution:
def sortByReflection(self, nums: List[int]) -> List[int]:
def f(x: int) -> int:
y = 0
while x:
y = y << 1 | (x & 1)
x >>= 1
return y
nums.sort(key=lambda x: (f(x), x))
return numsclass Solution {
public int[] sortByReflection(int[] nums) {
int n = nums.length;
Integer[] a = new Integer[n];
Arrays.setAll(a, i -> nums[i]);
Arrays.sort(a, (u, v) -> {
int fu = f(u);
int fv = f(v);
if (fu != fv) {
return Integer.compare(fu, fv);
}
return Integer.compare(u, v);
});
for (int i = 0; i < n; i++) nums[i] = a[i];
return nums;
}
private int f(int x) {
int y = 0;
while (x != 0) {
y = (y << 1) | (x & 1);
x >>= 1;
}
return y;
}
}class Solution {
public:
vector<int> sortByReflection(vector<int>& nums) {
auto f = [](int x) {
int y = 0;
while (x) {
y = (y << 1) | (x & 1);
x >>= 1;
}
return y;
};
sort(nums.begin(), nums.end(), [&](int a, int b) {
int fa = f(a);
int fb = f(b);
if (fa != fb) {
return fa < fb;
}
return a < b;
});
return nums;
}
};function sortByReflection(nums: number[]): number[] {
const f = (x: number): number => {
let y = 0;
for (; x; x >>= 1) {
y = (y << 1) | (x & 1);
}
return y;
};
nums.sort((a, b) => {
const fa = f(a);
const fb = f(b);
if (fa !== fb) {
return fa - fb;
}
return a - b;
});
return nums;
}func sortByReflection(nums []int) []int {
f := func(x int) int {
y := 0
for x != 0 {
y = (y << 1) | (x & 1)
x >>= 1
}
return y
}
sort.Slice(nums, func(i, j int) bool {
fi := f(nums[i])
fj := f(nums[j])
if fi != fj {
return fi < fj
}
return nums[i] < nums[j]
})
return nums
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Reflection in Comparator | O(n log n * b) | O(1) | Simple implementation when input size is small and recomputation cost is negligible |
| Custom Sort with Precomputed Reflection Keys | O(n log n) | O(n) | Preferred solution for interviews and large arrays; avoids repeated reflection computation |
| Bitwise Reflection Key + Sort | O(n log n) | O(n) | When optimizing constant factors by avoiding string conversions during reflection |
Frequently asked questions
Is Sort Integers by Binary Reflection easy or hard?
Sort Integers by Binary Reflection is considered an easy problem. The main challenge is implementing the binary reflection correctly and applying custom sorting based on the transformed value.
Sort Integers by Binary Reflection Python/Java solution
In Python, use sorted(nums, key=reflection_function) where the key returns the reversed binary value. In Java, implement a custom Comparator or precompute reflection values and sort using Arrays.sort with a comparator referencing those keys.
How to solve Sort Integers by Binary Reflection in O(n)?
Achieving true O(n) sorting is generally not feasible because comparison-based sorting requires O(n log n). The typical solution computes binary reflections and sorts the array using those values as keys, resulting in O(n log n) time.
What is the best approach for Sort Integers by Binary Reflection?
The best approach is custom sorting with a precomputed binary reflection key. Compute the reflected value for each integer once, then sort the array using that value as the sorting key. This avoids repeated conversions inside the comparator and runs in O(n log n) time with O(n) extra space.
Is Sort Integers by Binary Reflection asked at Google/Amazon/Meta?
Variants of custom sorting problems appear frequently in interviews at companies like Google, Amazon, and Meta. They test whether candidates can design comparator logic or transform values into sortable keys efficiently.
What data structure is used in Sort Integers by Binary Reflection?
The main structure is an array combined with a sorting algorithm that supports custom comparison or key functions. Some implementations also use auxiliary arrays or maps to store precomputed reflection values for each element.
What is the time complexity of Sort Integers by Binary Reflection?
The optimal solution runs in O(n log n) time because the array must be sorted. Computing the reflection for each integer adds O(n * b), where b is the number of bits, which is small compared to sorting. Space complexity is O(n) if reflection keys are stored.