Find if Array Can Be Sorted - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given an array where you can swap two adjacent elements only if they have the same number of set bits in their binary representation. The task is to determine whether these restricted swaps are enough to make the entire array sorted in non-decreasing order.
Approach 1: Sort by Set Bits Count, Then Regular Sort (O(n log n) time, O(n) space)
The key observation: elements with different set-bit counts can never cross each other because swaps are allowed only when both numbers have the same bit count. That means the relative order of groups with different set-bit counts is fixed. First compute the number of set bits for each element using bit manipulation. Then create a copy of the array sorted normally. If the sorted array can be formed by only rearranging numbers inside segments that share the same bit count, the transformation is valid. This approach relies on grouping elements by their bit counts and verifying that each group can internally reorder to match the sorted target. Sorting dominates the runtime, giving O(n log n) time and O(n) extra space.
This method is straightforward and easy to implement using built-in sorting. It also highlights how constraints on swaps restrict movement across groups. It uses concepts from sorting and bit manipulation.
Approach 2: Simulating Swaps Using Set Bit Groups (O(n) time, O(1) space)
A more optimal solution comes from observing how these swap constraints partition the array. Adjacent elements with the same number of set bits effectively form a segment where arbitrary reordering is possible. Elements cannot move outside their segment if the neighboring numbers have different bit counts. Iterate through the array and identify contiguous groups where all numbers share the same set-bit count.
For each group, track the minimum and maximum value inside it. When moving to the next group, check whether the smallest value in the new group is at least as large as the maximum value from previous groups. If a later group contains a value smaller than a previous maximum, sorting is impossible because that element cannot cross the bit-count boundary. This single pass simulation determines feasibility in O(n) time and constant extra space.
The approach avoids explicit sorting and works by validating ordering constraints between segments. It relies heavily on fast bit counting and sequential array traversal, combining ideas from array processing and bit analysis.
Recommended for interviews: The linear scan using set-bit groups is what interviewers usually expect. The sorting-based approach demonstrates the core constraint correctly, but the O(n) segment validation shows deeper insight into how restricted swaps partition the array.
Approach 1: Approach 1: Sort by Set Bits Count, Then Regular Sort
This approach involves creating a mapping of numbers based on their set bits count. We group all numbers having the same set bits count and sort each group individually. If by concatenating these sorted groups in the order of their set bits count, we can get a sorted version of the original array, then we return true; otherwise, return false.
The implementation first calculates the number of set bits for each element in the array. We then utilize arrays akin to buckets to store elements based on their set bits count. Each bucket is then independently sorted. Finally, the sorted buckets are concatenated and checked for any overall sorting errors.
Complexity
Time Complexity: O(n log n), primarily due to the sorting step for each bucket.
Space Complexity: O(n), for the additional storage required for the bitCountBuckets.
Approach 2: Approach 2: Simulating Swaps Using Set Bit Groups
In this approach, we simulate the individual moves as described in the problem. We group numbers by their set bit counts and within each group, attempt sorting by simulating adjacent swaps. Finally, we attempt confirmation by juxtaposing against a globally sorted array.
By grouping in buckets and simulating as many allowed swaps as necessary within the grouping paradigm, we achieve a checkpoint against the globally sorted version.
Complexity
Time Complexity: O(n log n), due to multiple sorting.
Space Complexity: O(n).
Approach 3: Two Pointers
We can use two pointers to divide the array nums into several subarrays, each subarray containing elements with the same number of 1s 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.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort by Set Bits Count, Then Regular Sort | Time Complexity: O(n log n), primarily due to the sorting step for each bucket. |
| Approach 2: Simulating Swaps Using Set Bit Groups | Time Complexity: O(n log n), due to multiple sorting. |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort by Set Bits Count, Then Regular Sort | O(n log n) | O(n) | When you want a simple implementation using sorting to validate whether restricted swaps can produce the sorted array |
| Simulating Swaps Using Set Bit Groups | O(n) | O(1) | Best for interviews and optimal performance when scanning contiguous bit-count segments |
Video Solution
Find if Array Can Be Sorted - Leetcode 3011 - Python • NeetCodeIO • 10,354 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find if Array Can Be Sorted easy or hard?
Find if Array Can Be Sorted Python/Java solution
How to solve Find if Array Can Be Sorted in O(n)?
What is the best approach for Find if Array Can Be Sorted?
Is Find if Array Can Be Sorted asked at Google/Amazon/Meta?
What data structure is used in Find if Array Can Be Sorted?
What is the time complexity of Find if Array Can Be Sorted?
Ready to solve this problem?
Practice Find if Array Can Be Sorted with our built-in code editor and test cases.
Practice on FleetCode