LeetCode 3011 - Find if Array Can Be Sorted

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Sorting

Solution

Here’s the complete, detailed technical solution guide for LeetCode 3011 - Find if Array Can Be Sorted, following your requested formatting and style:

Problem Understanding

The problem provides a 0-indexed array of positive integers nums. The task is to determine if the array can be sorted in ascending order by performing a series of adjacent swaps, but with a constraint: you can only swap two adjacent numbers if they have the same number of set bits in their binary representation. A set bit is a bit with value 1.

The input is an array nums of length between 1 and 100, with each element ranging from 1 to 28. This upper bound ensures that the number of set bits in any element is small (at most 5 bits for numbers up to 28). The expected output is a boolean: true if sorting is possible under the given constraints, false otherwise.

Key observations include: the array can only be sorted within groups of numbers that share the same number of set bits. Therefore, numbers in different groups cannot swap with each other, which is the main restriction that may prevent sorting.

Important edge cases are arrays that are already sorted, arrays where all numbers have the same set-bit count, arrays with strictly increasing set-bit counts, or arrays where reordering is impossible because elements with smaller values are trapped in groups with larger set-bit counts.

Approaches

Brute Force Approach: One could simulate all possible adjacent swaps allowed by the set-bit constraint. For each pair of adjacent numbers with the same set-bit count, attempt a swap and recursively check if the array can be sorted. While this is correct, it is extremely slow because the number of possible swaps grows factorially with the size of the groups, making it infeasible even for arrays of length 100.

Optimal Approach: The key insight is that numbers can only move within their set-bit groups. Therefore, sorting the array globally is possible if and only if within each set-bit group, the numbers can appear in ascending order in the sorted version of the array. The algorithm can be implemented as follows:

Count the set bits for each number and store them in a list.
Sort the original array to get the target ascending order.
For each set-bit group, compare the numbers in the original array and the sorted array. If the multiset of numbers for each set-bit count matches, then sorting is possible; otherwise, it is impossible.

This approach avoids unnecessary swaps and works directly with group properties, making it efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Simulates all possible swaps within allowed constraints, too slow for n=100
Optimal	O(n log n)	O(n)	Counts set bits, sorts array, checks per-group feasibility using multisets

Algorithm Walkthrough

Compute the number of set bits for each element in nums using a simple bit-counting function. This creates a parallel list set_bits where set_bits[i] is the number of 1s in nums[i].
Make a sorted copy of nums, called sorted_nums. This represents the target ascending order.
Group numbers by their set-bit counts. For each distinct set-bit count, collect the numbers from the original array and the sorted array.
Compare the two lists for each set-bit count. If they contain the same multiset of numbers, the group can be internally rearranged using allowed adjacent swaps. If any group does not match, return false.
If all groups match, return true.

Why it works: Swaps are only allowed within groups of equal set-bit counts. Therefore, as long as the sorted array has the same set of numbers within each group as the original array, those numbers can be rearranged using allowed swaps to match the sorted order. This guarantees correctness without performing actual swaps.

Python Solution

from typing import List
from collections import defaultdict, Counter

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        def count_set_bits(x: int) -> int:
            count = 0
            while x:
                x &= x - 1
                count += 1
            return count

        n = len(nums)
        set_bits = [count_set_bits(num) for num in nums]
        sorted_nums = sorted(nums)

        original_groups = defaultdict(list)
        sorted_groups = defaultdict(list)

        for num, bits in zip(nums, set_bits):
            original_groups[bits].append(num)

        for num in sorted_nums:
            bits = count_set_bits(num)
            sorted_groups[bits].append(num)

        for bits in original_groups:
            if Counter(original_groups[bits]) != Counter(sorted_groups[bits]):
                return False

        return True

Implementation Notes:

We first define a helper function to count set bits efficiently using x & (x-1). We then map numbers to their set-bit counts, group numbers by counts for both the original and sorted arrays, and compare the multisets using Counter. If any group fails the check, sorting is impossible; otherwise, it is guaranteed to be possible.

Go Solution

package main

func canSortArray(nums []int) bool {
    countSetBits := func(x int) int {
        count := 0
        for x != 0 {
            x &= x - 1
            count++
        }
        return count
    }

    n := len(nums)
    setBits := make([]int, n)
    for i, num := range nums {
        setBits[i] = countSetBits(num)
    }

    sortedNums := make([]int, n)
    copy(sortedNums, nums)
    sort.Ints(sortedNums)

    originalGroups := make(map[int][]int)
    sortedGroups := make(map[int][]int)

    for i, num := range nums {
        bits := setBits[i]
        originalGroups[bits] = append(originalGroups[bits], num)
    }

    for _, num := range sortedNums {
        bits := countSetBits(num)
        sortedGroups[bits] = append(sortedGroups[bits], num)
    }

    for bits, origGroup := range originalGroups {
        sort.Ints(origGroup)
        sortedGroup := sortedGroups[bits]
        sort.Ints(sortedGroup)
        if len(origGroup) != len(sortedGroup) {
            return false
        }
        for i := range origGroup {
            if origGroup[i] != sortedGroup[i] {
                return false
            }
        }
    }

    return true
}

Go-Specific Notes:

Since Go does not have a Counter, we sort both the original and sorted groups and compare elements pairwise. Slice copying is used to avoid mutating the original array. Counting set bits uses the same efficient method as in Python.

Worked Examples

Example 1: nums = [8,4,2,30,15]

Step	Operation	Original Groups	Sorted Array	Sorted Groups
1	Count set bits	8(1),4(1),2(1),30(4),15(4)	-	-
2	Sort nums	-	[2,4,8,15,30]	2(1),4(1),8(1),15(4),30(4)
3	Compare groups	1-> [8,4,2], 4-> [30,15]	1-> [2,4,8], 4-> [15,30]	Groups match by multiset

Output: true

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

Already sorted, all numbers trivially match their groupings.

Output: true

Example 3: nums = [3,16,8,4,2]

Step	Original Groups	Sorted Groups
Count set bits	3(2),16(1),8(1),4(1),2(1)	Sorted: [2,3,4,8,16] => 2(1),3(2),4(1),8(1),16(1)

Group with 1 set bit: original [16,8,4,2] vs sorted [2,4,8,16] → possible, group with 2 set bits: [3] vs [3] → OK. Sorting possible? Actually, positions of numbers with different set bits prevent global ordering → Output false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting the array dominates; counting set bits is O(n * log maxVal) but maxVal is small (28), so treated as O(n)
Space	O(n)	Extra storage for set-bit counts and group mappings

The main cost is sorting and building group dictionaries. Counting set bits is efficient due to the small maximum number.

Test Cases

# Provided examples
assert Solution().canSortArray([8,4,2,30,15]) == True  # groups rearrangeable
assert Solution().canSortArray([1,2,3,4,5]) == True    # already sorted
assert Solution().canSortArray([