# Find if Array Can Be Sorted
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-if-array-can-be-sorted)
Canonical: https://scaleengineer.com/dsa/problems/find-if-array-can-be-sorted
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Edelweiss Group](https://scaleengineer.com/companies/edelweiss-group)
---
## Problem
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 <= 100`
* `1 <= nums[i] <= 28`

# Approaches
## Simulation using Bubble Sort
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.
**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.
**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.
### Explanation
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:
1. The elements are out of order (i.e., `nums[i] > nums[i+1]`).
2. 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's `Integer.bitCount()` is perfect for this.
```java
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;
    }
}
```
### Algorithm
- Use a `do-while` loop that continues as long as swaps are being made in a pass.
- Inside the loop, iterate from `i = 0` to `n-2`.
- For each `i`, check if `nums[i] > nums[i+1]`.
- If they are out of order, calculate the number of set bits for both `nums[i]` and `nums[i+1]`.
- If the bit counts are equal, swap `nums[i]` and `nums[i+1]` and set a flag indicating a swap occurred.
- After the `do-while` loop 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 any `i`, return `false`.
- If the final check passes, return `true`.

## Group by Bit Count and Sort
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.
**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)`.
**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.
### Explanation
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`.
```java
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;
    }
}
```
### Algorithm
- Initialize a pointer `i = 0`.
- While `i` is less than the array length `n`:
    a. Record the starting index of the current block, `start = i`.
    b. Get the bit count of `nums[i]`.
    c. Move `i` forward as long as `i < n` and the element `nums[i]` has the same bit count.
    d. Now, the block is from index `start` to `i-1`. Sort this sub-array `nums[start...i-1]`.
- After the loop, all blocks have been sorted in-place.
- Iterate from `k = 1` to `n-1` and check if `nums[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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 True

```