#3011

Medium

LeetCode Problem Workspace

Find if Array Can Be Sorted

Determine if a given array can be sorted using adjacent swaps restricted by equal set bits in binary representation.

Problem Statement

You are given a 0-indexed array of positive integers nums. In one operation, you may swap any two adjacent elements if and only if they have the same number of set bits in their binary representations. You can perform this operation any number of times, including zero.

Return true if it is possible to sort the array in strictly ascending order using the allowed operation. Otherwise, return false. Consider how grouping numbers by set bit counts affects the sorting strategy and feasibility.

Examples

Example 1

Input: nums = [8,4,2,30,15]

Output: true

Let's look at the binary representation of every element. The numbers 2, 4, and 8 have one set bit each with binary representation "10", "100", and "1000" respectively. The numbers 15 and 30 have four set bits each with binary representation "1111" and "11110". We can sort the array using 4 operations:

Swap nums[0] with nums[1]. This operation is valid because 8 and 4 have one set bit each. The array becomes [4,8,2,30,15].
Swap nums[1] with nums[2]. This operation is valid because 8 and 2 have one set bit each. The array becomes [4,2,8,30,15].
Swap nums[0] with nums[1]. This operation is valid because 4 and 2 have one set bit each. The array becomes [2,4,8,30,15].
Swap nums[3] with nums[4]. This operation is valid because 30 and 15 have four set bits each. The array becomes [2,4,8,15,30]. The array has become sorted, hence we return true. Note that there may be other sequences of operations which also sort the array.

Example 2

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

Output: true

The array is already sorted, hence we return true.

Example 3

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

Output: false

It can be shown that it is not possible to sort the input array using any number of operations.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 28

Solution Approach

Count set bits and group elements

Calculate the number of set bits for each element and create groups of elements that share the same set bit count. This step identifies segments where swaps are allowed.

Sort each segment individually

For each group, sort the elements within that segment. Swaps outside the segment are invalid, so sorting is restricted to elements with equal set bits.

Reconstruct and verify global order

Concatenate the sorted segments in their original relative order. If the resulting array is fully ascending, return true. If any element violates ascending order, return false.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each element is processed once for bit counting and segment sorting. Space complexity is O(n) due to storing groups of elements by set bit counts.

What Interviewers Usually Probe

Look for opportunities to segment the array by set bit counts.
Check if sorting within segments can lead to global ascending order.
Ask candidates about efficient ways to count set bits and map numbers to segments.

Common Pitfalls or Variants

Common pitfalls

Assuming any adjacent swap is allowed without checking set bit counts.
Overlooking that segments must maintain their original relative positions.
Failing to verify that the concatenated sorted segments form a fully ascending array.

Follow-up variants

Allow swaps for elements with set bits differing by one instead of exactly equal.
Determine the minimum number of swaps required to sort the array under the same rules.
Apply the same approach to arrays of larger integers with more than 28 bits.

FAQ

What does 'Find if Array Can Be Sorted' specifically require?

It requires checking if the array can become ascending by swapping only adjacent elements with equal set bits.

How do I count set bits efficiently for this problem?

Use built-in functions or bitwise operations like n & (n-1) in a loop to count set bits for each element.

Can the array already sorted return false?

No, if the array is already ascending, the answer is true regardless of set bit distribution.

What if two elements with different set bits are adjacent?

They cannot be swapped, so the relative order of such elements is fixed in any valid solution.

Does segmenting by set bits always guarantee sortability?

No, segments can be internally sortable, but the global order after concatenation might still fail ascending order.

terminal

Solution

Solution 1: Two Pointers

We can use two pointers to divide the array $\textit{nums}$ into several subarrays, each subarray containing elements with the same number of $1$s in their binary representation. For each subarray, we only need to focus on its maximum and minimum values. If the minimum value is less than the maximum value of the previous subarray, then it is impossible to make the array ordered by swapping.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        pre_mx = 0
        i, n = 0, len(nums)
        while i < n:
            cnt = nums[i].bit_count()
            j = i + 1
            mi = mx = nums[i]
            while j < n and nums[j].bit_count() == cnt:
                mi = min(mi, nums[j])
                mx = max(mx, nums[j])
                j += 1
            if pre_mx > mi:
                return False
            pre_mx = mx
            i = j
        return True

Continue Practicing

#3068 find the maximum sum of node values #2708 maximum strength of a group #2135 count words obtained after adding a letter