Problem Description

You have an array of positive integers where each element can be represented in binary form. The problem asks whether you can sort this array in ascending order using a specific type of swap operation.

The key constraint is that you can only swap two adjacent elements if they have the same number of set bits (1s in their binary representation). For example:

• 5 in binary is 101 (has 2 set bits)
• 3 in binary is 011 (has 2 set bits)
• Since both have 2 set bits, you could swap them if they were adjacent

You can perform this swap operation as many times as needed, including zero times.

The goal is to determine if it's possible to sort the entire array in ascending order using only these restricted swaps. Return true if the array can be sorted this way, or false if it's impossible.

For example, if you have [8, 4, 2, 30, 15]:

• 8 = 1000 (1 set bit)
• 4 = 100 (1 set bit)
• 2 = 10 (1 set bit)
• 30 = 11110 (4 set bits)
• 15 = 1111 (4 set bits)

Elements with the same bit count can be rearranged among themselves through adjacent swaps, but elements with different bit counts cannot pass each other. This creates "blocks" of elements that must maintain their relative order to other blocks.

Intuition

Since we can only swap adjacent elements with the same number of set bits, elements with different bit counts cannot "pass through" each other. This creates natural boundaries in the array - imagine the array being divided into blocks where each block contains elements with the same bit count.

Within each block, we can rearrange elements freely through adjacent swaps (like bubble sort). This means each block can be internally sorted. However, the blocks themselves must remain in their original relative positions.

For the array to be sortable, we need the following condition: when we sort each block internally, the resulting array should be globally sorted. This happens if and only if the maximum value in each block is less than or equal to the minimum value in the next block.

Think of it this way: if block A comes before block B, and block A's maximum value is greater than block B's minimum value, then these two values are "out of order" globally. Since they have different bit counts, they can never swap positions, making it impossible to sort the array.

The key insight is that we don't need to actually perform the swaps. We just need to:

1. Group consecutive elements with the same bit count
2. Find the minimum and maximum value in each group
3. Check if the maximum of each group is less than or equal to the minimum of the next group

If this condition holds for all consecutive groups, the array can be sorted. Otherwise, it cannot.

Learn more about Sorting patterns.

Solution Approach

The solution uses a two-pointer technique to process the array in groups of elements with the same bit count.

We maintain several key variables:

• pre_mx: Tracks the maximum value from all previously processed groups
• i: Starting index of the current group
• mi and mx: Minimum and maximum values in the current group

The algorithm works as follows:

1. Initialize tracking variables: Set pre_mx = 0 to track the maximum value seen in previous groups, and start with i = 0.

2. Process each group: For each position i, we:

   • Calculate the bit count of nums[i] using bit_count()
   • Initialize mi and mx with nums[i]
   • Use pointer j to find all consecutive elements with the same bit count

3. Expand the current group: Starting from j = i + 1, we continue adding elements to the current group while they have the same bit count:

   while j < n and nums[j].bit_count() == cnt:
       mi = min(mi, nums[j])
       mx = max(mx, nums[j])
       j += 1

4. Check the sorting condition: After identifying a complete group, we verify if pre_mx > mi. If true, it means the maximum value from previous groups is greater than the minimum value of the current group. This violates the sorting requirement, so we return False.

5. Update for next iteration:

   • Update pre_mx = mx to track the new maximum value seen so far
   • Move i = j to start processing the next group

6. Return result: If we process all groups without finding any violations, return True.

The time complexity is O(n) as we visit each element exactly once. The space complexity is O(1) since we only use a constant amount of extra variables.

Example Walkthrough

Let's walk through the array [3, 16, 8, 4, 2] to see if it can be sorted.

First, let's identify the bit counts:

• 3 = 11 (2 set bits)
• 16 = 10000 (1 set bit)
• 8 = 1000 (1 set bit)
• 4 = 100 (1 set bit)
• 2 = 10 (1 set bit)

Step 1: Process first group (i=0)

• Start with nums[0] = 3, bit count = 2
• Initialize: mi = 3, mx = 3
• Check nums[1] = 16: bit count = 1 (different from 2)
• Group ends at index 0
• Group contains: [3] with min=3, max=3
• Check condition: pre_mx (0) > mi (3)? No, continue
• Update: pre_mx = 3, i = 1

Step 2: Process second group (i=1)

• Start with nums[1] = 16, bit count = 1
• Initialize: mi = 16, mx = 16
• Check remaining elements:
  • nums[2] = 8: bit count = 1 (same), update mi = 8, mx = 16
  • nums[3] = 4: bit count = 1 (same), update mi = 4, mx = 16
  • nums[4] = 2: bit count = 1 (same), update mi = 2, mx = 16
• Group contains: [16, 8, 4, 2] with min=2, max=16
• Check condition: pre_mx (3) > mi (2)? Yes!
• Return False

The array cannot be sorted because the element 3 (from the first group with 2 set bits) needs to come after 2 (from the second group with 1 set bit) in the sorted order. Since they have different bit counts, they cannot swap positions through adjacent swaps.

To visualize why this fails: if we could sort within groups, we'd have:

• Group 1: [3] (already sorted)
• Group 2: [2, 4, 8, 16] (sorted within group)
• Result: [3, 2, 4, 8, 16] - not globally sorted!

For comparison, the array [8, 4, 2, 30, 15] would return True because:

• Group 1 (1 bit): [8, 4, 2] → sorted becomes [2, 4, 8], max=8
• Group 2 (4 bits): [30, 15] → sorted becomes [15, 30], min=15
• Since 8 < 15, the condition is satisfied and the final result [2, 4, 8, 15, 30] is globally sorted.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The algorithm uses a two-pointer approach with variables i and j. The outer while loop starts with i = 0 and continues while i < n. The inner while loop moves j forward to find consecutive elements with the same bit count. The key observation is that each element in the array is visited exactly once by the pointer j. When j reaches the end of a group with the same bit count, i jumps directly to j, skipping all elements that were already processed. Therefore, despite having nested loops, each element is processed only once, resulting in a linear time complexity of O(n).

Space Complexity: O(1).

The algorithm only uses a constant amount of extra space regardless of the input size. The variables used are:

• pre_mx: stores the maximum value of the previous group
• i, j, n: loop counters and array length
• cnt: stores the bit count of the current group
• mi, mx: stores the minimum and maximum values of the current group

All these variables occupy constant space that doesn't scale with the input size, hence the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Assuming Non-Adjacent Elements Can Be Compared

A common mistake is thinking that if two elements have the same bit count, they can be swapped regardless of their positions. This leads to incorrect solutions that try to sort all elements with the same bit count together, ignoring the adjacency requirement.

Incorrect approach:

# WRONG: Groups all elements by bit count, ignoring position
def canSortArray(nums):
    bit_groups = {}
    for num in nums:
        bits = num.bit_count()
        if bits not in bit_groups:
            bit_groups[bits] = []
        bit_groups[bits].append(num)
  
    # This doesn't consider that elements must be adjacent to swap

Why it fails: Elements with the same bit count that are separated by elements with different bit counts cannot be swapped. For example, in [3, 16, 8, 4, 2], the values 3 and 2 both have 2 set bits, but they cannot be swapped because they're separated by elements with 1 set bit.

2. Not Maintaining Proper Group Boundaries

Another pitfall is failing to correctly identify where one group ends and another begins, especially when updating the loop index.

Incorrect approach:

# WRONG: Increments index by 1 instead of jumping to next group
def canSortArray(nums):
    prev_max = 0
    i = 0
    while i < len(nums):
        # ... process group ...
        i += 1  # WRONG: Should be i = j

Solution: Always update the index to skip past the entire processed group:

while i < len(nums):
    # Find group boundary at j
    j = i + 1
    while j < len(nums) and nums[j].bit_count() == nums[i].bit_count():
        j += 1
    # ... check conditions ...
    i = j  # CORRECT: Jump to start of next group

3. Forgetting to Track Both Min and Max Within Groups

Some solutions only track the maximum value of each group but forget that we need both the minimum and maximum to properly validate the sorting condition.

Incorrect approach:

# WRONG: Only tracks maximum, missing minimum check
def canSortArray(nums):
    prev_max = 0
    for num in nums:
        if num < prev_max and different_bit_count:
            return False
        prev_max = max(prev_max, num)

Solution: Always track both minimum and maximum for each group:

# Track both min and max for current group
group_min = nums[i]
group_max = nums[i]
while j < len(nums) and nums[j].bit_count() == current_bit_count:
    group_min = min(group_min, nums[j])
    group_max = max(group_max, nums[j])
    j += 1

4. Edge Case: Single Element Groups

Failing to properly handle groups with only one element can lead to bugs in the min/max initialization or boundary checking.

Solution: Initialize both group_min and group_max with the first element of the group before entering the expansion loop. This ensures single-element groups are handled correctly without special casing.