LeetCode 3769 - Sort Integers by Binary Reflection

LeetCode Problem 3769

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

This problem asks us to sort an array of positive integers based on a transformation called binary reflection. The binary reflection of a number is obtained by converting the number to its binary representation, reversing the order of the bits (ignoring leading zeros), and then interpreting the resulting binary string as a decimal integer. For example, the binary reflection of 4 is obtained by converting 4 to binary (100), reversing it to 001, which is 1 in decimal.

The input is an array of integers nums with length between 1 and 100, and each integer is between 1 and 1,000,000,000. The output is the array sorted in ascending order by the binary reflections. If two numbers have the same reflected value, the smaller original number comes first.

Key points include handling repeated numbers correctly, ensuring leading zeros do not affect the reflection, and correctly sorting numbers with the same reflected value by the original number. A naive approach could mismanage ties or incorrectly compute the reflection if leading zeros are not ignored.

Important edge cases include arrays where multiple numbers share the same reflected value, arrays containing the minimum or maximum allowed integer, and arrays of length 1.

Approaches

A brute-force approach would involve computing the binary reflection for each number, storing it alongside the original number in a list of tuples, and then sorting this list based on the reflected values, breaking ties using the original number. This works and is correct because it directly implements the problem definition, but it involves extra memory and repeated conversions if not careful.

The optimal approach follows the same strategy, but leverages Python’s built-in sort stability or Go’s custom comparator to sort the array in-place using a lambda function or comparator that computes the reflected value on demand. Given the constraints (n <= 100), this is already efficient, as the number of bits in each integer is at most 30, making reflection computation trivial.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n * k)	O(n)	Convert each number to binary, reverse, sort by reflected value with tie-breaker
Optimal	O(n log n * k)	O(n)	Use sort with a custom key/comparator; reflection is computed inline; very similar to brute force for small n

k here is the maximum number of bits in a number, up to 30 for numbers ≤ 10^9.

Algorithm Walkthrough

1. Iterate over each number in the array. Convert the number to its binary representation using a standard method, ignoring the 0b prefix.
2. Reverse the binary string. Remove any leading zeros after reversal to get the canonical reflected binary number.
3. Convert the reversed binary string back to an integer to obtain the reflected value.
4. Pair each original number with its reflected value, forming tuples (reflected_value, original_number).
5. Sort the array of tuples. Python’s default tuple comparison or Go’s comparator will first sort by reflected_value, and if there is a tie, by original_number.
6. Extract the original numbers from the sorted tuples to form the final sorted array.

Why it works: Sorting tuples using the reflected value as the primary key guarantees the ascending order based on reflection. Using the original number as the secondary key correctly resolves ties. Python’s sort is stable, ensuring that the relative order of numbers with the same reflection is consistent.

Python Solution

from typing import List

class Solution:
    def sortByReflection(self, nums: List[int]) -> List[int]:
        def reflect(n: int) -> int:
            # Convert number to binary, remove '0b', reverse string, then convert back to int
            return int(bin(n)[2:][::-1], 2)
        
        # Sort nums using reflected value as primary key, original number as secondary key
        return sorted(nums, key=lambda x: (reflect(x), x))

The reflect function handles converting a number to binary, reversing it, and returning the reflected decimal value. The sorted function uses a lambda that returns a tuple of (reflected_value, original_number) so the sort respects both the reflected value and tie-breaker rules.

Go Solution

import (
    "sort"
    "strconv"
)

func reflect(n int) int {
    binStr := strconv.FormatInt(int64(n), 2)
    rev := []rune(binStr)
    for i, j := 0, len(rev)-1; i < j; i, j = i+1, j-1 {
        rev[i], rev[j] = rev[j], rev[i]
    }
    reflected, _ := strconv.ParseInt(string(rev), 2, 64)
    return int(reflected)
}

func sortByReflection(nums []int) []int {
    sort.Slice(nums, func(i, j int) bool {
        ri, rj := reflect(nums[i]), reflect(nums[j])
        if ri == rj {
            return nums[i] < nums[j]
        }
        return ri < rj
    })
    return nums
}

In Go, we convert integers to binary strings using strconv.FormatInt, reverse the rune slice, parse it back to an integer, and use sort.Slice with a custom comparator that handles tie-breaking based on the original numbers.

Worked Examples

Example 1: nums = [4,5,4]

Number	Binary	Reversed Binary	Reflected Value
4	100	001	1
5	101	101	5
4	100	001	1

Sort by reflected value: [1,1,5] → original numbers: [4,4,5]

Example 2: nums = [3,6,5,8]

Number	Binary	Reversed Binary	Reflected Value
3	11	11	3
6	110	011	3
5	101	101	5
8	1000	0001	1

Sorted reflected values: 1,3,3,5 → original numbers: [8,3,6,5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n * k)	Computing the reflection takes O(k) per number (k <= 30), sorting n numbers takes O(n log n)
Space	O(n)	Storing the reflected values or using a sort key requires O(n) extra space

Because n ≤ 100 and k ≤ 30, this solution is efficient in practice.

Test Cases

# Provided examples
assert Solution().sortByReflection([4,5,4]) == [4,4,5]  # duplicate numbers
assert Solution().sortByReflection([3,6,5,8]) == [8,3,6,5]  # tie on reflection

# Edge cases
assert Solution().sortByReflection([1]) == [1]  # single element
assert Solution().sortByReflection([1,2,4,8]) == [8,4,2,1]  # increasing powers of 2
assert Solution().sortByReflection([7,7,7]) == [7,7,7]  # all same numbers

# Tie-breaker test
assert Solution().sortByReflection([6,3]) == [3,6]  # both reflect to 3, original order by value

Test	Why
[4,5,4]	Handles duplicate numbers and correct reflection ordering
[3,6,5,8]	Tie-breaking when reflected values are equal
[1]	Minimal input size
[1,2,4,8]	Powers of two with leading zeros after reflection
[7,7,7]	All numbers identical
[6,3]	Tie-breaking by original number

Edge Cases

Single element array: An array with only one element must return itself. The algorithm handles this because sorting a single element is trivially correct.

Numbers with leading zeros after reversal: Powers of two such as 8, 4, 2 when reversed produce leading zeros. The algorithm correctly ignores leading zeros when parsing back to integer, ensuring reflections are computed accurately.

Duplicate numbers with same reflection: When multiple numbers have the same reflected value, the tie-breaker rule using the original number ensures that the final ordering is correct. Python’s stable sort or Go’s comparator guarantees this property is maintained.