Find if Array Can Be Sorted
MedPrompt
You are given a 0-indexed array of positive integers nums.
In one operation, you can swap any two adjacent elements if they have the same number of set bits. You are allowed to do this operation any number of times (including zero).
Return true if you can sort the array in ascending order, else return false.
Example 1:
Input: nums = [8,4,2,30,15]
Output: true
Explanation: 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
Explanation: The array is already sorted, hence we return true.Example 3:
Input: nums = [3,16,8,4,2]
Output: false
Explanation: It can be shown that it is not possible to sort the input array using any number of operations.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 28
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the sorting process directly. Since we can swap adjacent elements with the same number of set bits as many times as we want, this is equivalent to being able to fully sort any contiguous sub-array of such elements. A modified bubble sort can achieve this. We repeatedly pass through the array, swapping adjacent elements nums[i] and nums[i+1] if nums[i] > nums[i+1] and they have the same bit count. We continue this until a full pass completes with no swaps. Finally, we check if the resulting array is sorted.
Algorithm
- Use a
do-whileloop that continues as long as swaps are being made in a pass. - Inside the loop, iterate from
i = 0ton-2. - For each
i, check ifnums[i] > nums[i+1]. - If they are out of order, calculate the number of set bits for both
nums[i]andnums[i+1]. - If the bit counts are equal, swap
nums[i]andnums[i+1]and set a flag indicating a swap occurred. - After the
do-whileloop terminates, the array is sorted as much as possible. - Perform a final linear scan to check if the array is fully sorted. If
nums[i] > nums[i+1]for anyi, returnfalse. - If the final check passes, return
true.
Walkthrough
The core idea is to mimic the allowed operations to get the array as sorted as possible. We can use a modified version of the bubble sort algorithm. A standard bubble sort makes multiple passes over the array, comparing adjacent elements and swapping them if they are in the wrong order. In our modified version, a swap is only performed if two conditions are met:
- The elements are out of order (i.e.,
nums[i] > nums[i+1]). - The elements have the same number of set bits.
We continue making passes over the array until no more swaps can be performed. This indicates that all contiguous groups of elements with the same bit count are internally sorted.
After the simulation, we perform a final check to see if the entire array is in non-decreasing order. If it is, the original array could be sorted; otherwise, it could not.
A helper function
countSetBits(n)is used to calculate the number of set bits (population count) of an integer. Java'sInteger.bitCount()is perfect for this.
class Solution { public boolean canSortArray(int[] nums) { int n = nums.length; boolean swapped; do { swapped = false; for (int i = 0; i < n - 1; i++) { if (nums[i] > nums[i+1] && Integer.bitCount(nums[i]) == Integer.bitCount(nums[i+1])) { int temp = nums[i]; nums[i] = nums[i+1]; nums[i+1] = temp; swapped = true; } } } while (swapped); for (int i = 0; i < n - 1; i++) { if (nums[i] > nums[i+1]) { return false; } } return true; }}Complexity
Time
`O(n^2)`. The `do-while` loop can run up to `n` times in the worst case, and the inner `for` loop runs `n-1` times. `Integer.bitCount()` is a constant time operation for 32-bit integers.
Space
`O(1)`. The sorting is done in-place, requiring no extra space proportional to the input size.
Trade-offs
Pros
Simple to understand and implement, as it's a small modification of a classic sorting algorithm.
It operates in-place, leading to low space complexity.
Cons
Less efficient than the optimal approach, with a time complexity of
O(n^2).For larger arrays, this approach would be too slow.
A more efficient approach recognizes that the ability to swap adjacent elements with the same bit count means we can fully sort any contiguous sub-array of such elements. The problem then simplifies to partitioning the array into contiguous blocks where elements in each block have the same bit count, sorting each block individually, and then checking if the entire array is sorted.
Algorithm
- Initialize a pointer
i = 0. - While
iis less than the array lengthn: a. Record the starting index of the current block,start = i. b. Get the bit count ofnums[i]. c. Moveiforward as long asi < nand the elementnums[i]has the same bit count. d. Now, the block is from indexstarttoi-1. Sort this sub-arraynums[start...i-1]. - After the loop, all blocks have been sorted in-place.
- Iterate from
k = 1ton-1and check ifnums[k] < nums[k-1]. - If this condition is ever met, return
false. - If the loop completes without finding any out-of-order elements, return
true.
Walkthrough
The key insight is that the relative order of elements can only be changed within contiguous groups that share the same number of set bits. The groups themselves cannot be reordered.
For the final array to be sorted, each of these groups must be sorted internally, and the resulting concatenated groups must form a sorted sequence.
The algorithm proceeds by identifying these contiguous blocks. We can iterate through the array with a pointer i. For each i, we find the end of the block, j, such that all elements from nums[i] to nums[j] have the same bit count.
Once a block nums[i...j] is identified, we sort just this sub-array.
We then continue this process from j+1 until the entire array has been processed.
After all such blocks are sorted, we do a final pass over the modified nums array to verify if it's globally sorted. If nums[k] < nums[k-1] for any k, it's impossible to sort the original array, so we return false. Otherwise, we return true.
import java.util.Arrays; class Solution { public boolean canSortArray(int[] nums) { int n = nums.length; int i = 0; while (i < n) { int start = i; int bitCount = Integer.bitCount(nums[i]); i++; while (i < n && Integer.bitCount(nums[i]) == bitCount) { i++; } // Sort the subarray from start to i-1 Arrays.sort(nums, start, i); } // Check if the array is sorted for (int k = 1; k < n; k++) { if (nums[k] < nums[k-1]) { return false; } } return true; }}Complexity
Time
`O(n log n)`. The process of finding blocks takes `O(n)` time in total. The sorting step dominates. If the block sizes are `k_1, k_2, ...`, the total time is `Σ O(k_i log k_i)`. In the worst case, this is `O(n log n)` when all elements form a single block.
Space
`O(log n)` on average. The space is used by the sorting algorithm's recursion stack. `Arrays.sort` in Java for primitives uses a dual-pivot quicksort which has an average space complexity of `O(log n)`. In the worst case, it can be `O(n)`.
Trade-offs
Pros
More efficient with a time complexity of
O(n log n).It correctly models the problem's core constraint about sortable groups.
Cons
Slightly more complex to implement than the bubble sort simulation due to managing sub-array indices and sorting.
Solutions
Solution
class Solution {public boolean canSortArray(int[] nums) { int preMx = -300; int i = 0, n = nums.length; while (i < n) { int j = i + 1; int cnt = Integer.bitCount(nums[i]); int mi = nums[i], mx = nums[i]; while (j < n && Integer.bitCount(nums[j]) == cnt) { mi = Math.min(mi, nums[j]); mx = Math.max(mx, nums[j]); j++; } if (preMx > mi) { return false; } preMx = mx; i = j; } return true; }}class Solution {public: bool canSortArray(vector<int> &nums) { int preMx = -300; int i = 0, n = nums.size(); while (i < n) { int j = i + 1; int cnt = __builtin_popcount(nums[i]); int mi = nums[i], mx = nums[i]; while (j < n && __builtin_popcount(nums[j]) == cnt) { mi = min(mi, nums[j]); mx = max(mx, nums[j]); j++; } if (preMx > mi) { return false; } preMx = mx; i = j; } return true; }};class Solution: def canSortArray(self, nums: List[int]) -> bool: pre_mx = - inf i, n = 0, len(nums) while i < n: j = i + 1 cnt = nums[i]. bit_count() 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 TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.