3011. Find if Array Can Be Sorted

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, 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 <= 100
• 1 <= nums[i] <= 28

Approach 01:

#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        int previousSetBits = 0;
        int previousMax = INT_MIN;  // The maximum of the previous segment
        int currentMax = INT_MIN;   // The maximum of the current segment
        int currentMin = INT_MAX;   // The minimum of the current segment

        for (const int number : nums) {
            int setBitsCount = __builtin_popcount(number);
            if (setBitsCount != previousSetBits) {  // Start a new segment
                if (previousMax > currentMin)
                    return false;
                previousSetBits = setBitsCount;
                previousMax = currentMax;
                currentMax = number;
                currentMin = number;
            } else {  // Continue with the current segment
                currentMax = max(currentMax, number);
                currentMin = min(currentMin, number);
            }
        }

        return previousMax <= currentMin;
    }
};

from typing import List

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        previousSetBits = 0
        previousMax = float('-inf')  # The maximum of the previous segment
        currentMax = float('-inf')   # The maximum of the current segment
        currentMin = float('inf')    # The minimum of the current segment

        for number in nums:
            setBitsCount = bin(number).count('1')
            if setBitsCount != previousSetBits:  # Start a new segment
                if previousMax > currentMin:
                    return False
                previousSetBits = setBitsCount
                previousMax = currentMax
                currentMax = number
                currentMin = number
            else:  # Continue with the current segment
                currentMax = max(currentMax, number)
                currentMin = min(currentMin, number)

        return previousMax <= currentMin

Time Complexity

• Loop Over Array:

  The function iterates through each element in nums once to determine if the array can be sorted as per the segment rules. Therefore, the main loop runs in \( O(N) \) time, where \( N \) is the size of the nums array.

• Bit Count Calculation:

  The function uses __builtin_popcount for each element, which has \( O(\log(\text{number of bits})) \) complexity. However, since the maximum bits in an integer are fixed, this operation is effectively \( O(1) \).

• Overall Time Complexity:

  The overall time complexity is \( O(N) \).

Space Complexity

• Auxiliary Variables:

  The function uses a constant amount of additional space for variables such as previousSetBits, previousMax, currentMax, and currentMin, all of which have \( O(1) \) space complexity.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).