Find if Array Can Be Sorted

Find if Array Can Be Sorted

What is this problem about?

The Find if Array Can Be Sorted interview question asks if you can sort an array by only swapping adjacent elements that have the same number of "set bits" (the number of 1s in their binary representation). You can perform as many swaps as needed. If the array can eventually be made non-decreasing, return true.

Why is this asked in interviews?

This Find if Array Can Be Sorted coding problem is a favorite at Microsoft and Meta. It tests your ability to recognize how local constraints affect global properties. It combines Bit Manipulation with Sorting or Grouping patterns. The key insight is that elements with the same set bit count can be reordered in any way among themselves, acting as a single movable "block."

Algorithmic pattern used

This problem uses Group-based Sorting Analysis.

1. Divide the array into contiguous segments where all elements in a segment have the same number of set bits.
2. For each segment, find its minimum and maximum values.
3. The array is sortable if and only if the maximum value of any segment is less than or equal to the minimum value of the immediately following segment.
4. This works because elements within a segment can be sorted (like Bubble Sort), but they cannot jump over an element with a different bit count.

Example explanation

Array: [8, 4, 2, 30, 15]

1. Set Bits: 8(1), 4(1), 2(1), 30(4), 15(4).
2. Groups:
   • Group 1: [8, 4, 2]. Min=2, Max=8. (Can be sorted to 2,4,8).
   • Group 2: [30, 15]. Min=15, Max=30. (Can be sorted to 15,30).
3. Check Transitions: Max of Group 1 (8) is $\le$ Min of Group 2 (15). Result: True.

Common mistakes candidates make

• Actual Simulation: Trying to implement a full sorting algorithm with custom swap rules. While this works, the "block" comparison logic is much faster and simpler.
• Miscounting Bits: Using an inefficient bit-counting method. Modern languages have built-in functions like Integer.bitCount() or bin(n).count('1').
• Ignoring Contiguity: Forgetting that you can only swap adjacent elements.

Interview preparation tip

Whenever a problem involves "swapping adjacent elements under condition X," look for invariants. Usually, this means the array is partitioned into segments that can be internally sorted but cannot mix with other segments.