3011. Find if Array Can Be Sorted

Problem Description

In this problem, we are given an array of positive integers called nums, and our task is to determine if we can sort it using a specific operation. The operation allows us to swap any two adjacent elements, but only if those elements have the same number of 1s in their binary representations; this is known as the number of set bits. We can perform this operation as many times as needed, including not at all, if the array is already sorted.

In essence, we need to check if, by using the allowed swaps, we can arrange the array in non-decreasing order. If we find it's possible to achieve this, we should return true. Otherwise, we return false if it's impossible to sort the array under these constraints.

Intuition

The solution hinges on understanding that we cannot change the relative order of elements with different numbers of set bits since they can't be swapped directly based on the rule. Therefore, sorting the array essentially breaks it down into subarrays, each composed of elements with the same number of set bits, which could be ordered in any way since swaps among them are allowed.

With this in mind, we can iterate through the array and identify these subarrays. Within each subarray, we keep track of the minimum and maximum value encountered so far. A crucial insight is that if the minimum value in a subarray is less than the maximum value of the previous subarray, it indicates that sorting is impossible. This is because, in a sorted array, all elements in a previous (and thus lower) subarray should be less than or equal to all the elements in the following subarray.

To implement this, we use two pointers as we traverse the array. The first pointer, i, marks the start of a subarray, and the second pointer, j, explores the rest of the array to find the end of this subarray. The while loops ensure that we progress through the array, from one subarray to the next, assessing the minimum and maximum for each set bit count. If we successfully traverse the entire array without encountering a condition that makes sorting impossible, we return true. Otherwise, we return false as soon as such a condition is found.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a straightforward two-pointer approach to tackle the problem:

1. Initialize a variable pre_mx to negative infinity. This will keep track of the maximum value of the previous subarray as we progress through nums.

2. Set up two pointers, i and j, starting from 0 (i) and 1 (j), respectively. Pointer i represents the beginning of the current subarray, while j will be used to find the end of this subarray.

3. Loop over nums using i to iterate through the array. For each position i, we: a. Find the number of set bits of nums[i], which determines the current subarray we're evaluating. This can be done using the .bit_count() method in Python. b. Initialize mi and mx to the value of nums[i]. These will track the minimum and maximum values within the current subarray, respectively.

4. While inside the loop, initiate a nested loop that keeps running as long as j is within the bounds of the array and nums[j] shares the same number of set bits as nums[i]. Within this loop: a. Update mi and mx to be the minimum and maximum of the current subarray by comparing them to nums[j]. b. Increment j to check the next element.

5. After the nested loop terminates (meaning we reached the end of the current subarray with matching set bits), check if pre_mx is greater than mi. If it is, it means that the previous subarray had a value greater than the smallest value of the current subarray, which implies it is impossible to sort the array. Hence, return False.

6. Update pre_mx with the largest value in the current subarray, mx, because this now becomes the maximum of the last processed subarray for the next iteration.

7. Set pointer i to j to start the algorithm for the next subarray of elements with equal set bit count.

8. If the algorithm completes the iteration over the array without returning False, it means sorting the array is possible under the given rules, so it returns True.

This approach efficiently applies the rules of the problem to determine if sorting is feasible, relying on the fact that only elements with the same number of set bits can be adjacent in the final sorted array. It uses python's built-in .bit_count() method to count set bits and utilizes comparison operations to ensure order within and between identified subarrays.

Example Walkthrough

Let's illustrate the solution approach using a small example with the array nums = [3, 1, 2, 4]. The binary representations are 11, 01, 10, and 100, with set bit counts of 2, 1, 1, and 1, respectively.

1. Initialize pre_mx to negative infinity. Start with i = 0 and j = 1.

2. At i = 0, nums[i] = 3. Number of set bits in 3 (11 in binary) is 2. Initialize min (mi) and max (mx) of the current subarray to the value of nums[i] which is 3.

3. Move to j which is 1. Number of set bits in nums[j] (1 in binary) is 1, which is different from the 2 set bits we have for nums[i]. So we close this subarray here because we cannot form a subarray with different set bit counts. Since we cannot include nums[j] in the current subarray, we skip updating mi and mx and proceed to step 5.

4. We check if pre_mx > mi which means if -inf > 3. This is not true, so we move on and update pre_mx to mx which is 3.

5. We set i to j, therefore i is now 1 and increment j to 2 to start evaluating the next subarray.

6. At i = 1, nums[i] is 1. The number of set bits is 1. Initialize mi and mx to 1.

7. j = 2, nums[j] = 2 which also has 1 set bit. We include nums[j] in the current subarray and update mi to min(mi, nums[j]) (which remains 1) and mx to max(mx, nums[j]) (which becomes 2). Increment j to 3.

8. j = 3, nums[j] = 4 which also has 1 set bit. We include nums[j] in the current subarray and update mi to min(mi, nums[j]) (which is still 1) and mx to max(mx, nums[j]) (which becomes 4). After this, j is out of bounds (since nums has only four elements), so we exit this nested loop.

9. We check if pre_mx > mi which means if 3 > 1. This is not true, so we update pre_mx to mx which is now 4.

10. Since we've reached the end of the array, we've verified that each subarray with the same set bit count is such that its minimum value is not less than the maximum value of the previous subarray.

The result here is that the array can be sorted using the allowed operations: swap 1 and 2 to get [3, 2, 1, 4], which is now in the non-decreasing order. Our algorithm returns True.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n) because there is a single while loop that iterates through each element of the array nums exactly once. Inside the loop, the .bit_count() method is called, which is expected to run in constant time, and basic arithmetic operations and comparisons are performed, which also take constant time per iteration. Even though there is a nested loop, it does not increase the overall number of iterations; it just continues from where the outer loop left off.

Space Complexity

The space complexity of the code is O(1) since it uses a fixed amount of extra space: variables pre_mx, i, n, j, cnt, mi, and mx. There is no use of any data structures that grow with the size of the input array nums, which keeps the space complexity constant.

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