• Posts

Problem 3011 Find if Array Can Be Sorted

Problem Statement

Link - Problem 3011

Question

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

Solution

class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        int set_bits = __builtin_popcount(nums[0]);
        int curr_max = nums[0], curr_min = nums[0], prev_max = INT_MIN;

        for(int i=1;i<nums.size();i++){
            if(__builtin_popcount(nums[i])==set_bits){
                curr_max = max(curr_max,nums[i]);
                curr_min = min(curr_min,nums[i]);
            }
            else {
                if(curr_min<prev_max)
                    return false;

                prev_max = curr_max;
                curr_max = nums[i];
                curr_min = nums[i];
                set_bits = __builtin_popcount(nums[i]);
            }
        }
        if(curr_min<prev_max)
                return false;

        return true;
    }
};

Complexity Analysis

| Algorithm             | Time Complexity | Space Complexity |
| --------------------- | --------------- | ---------------- |
| Single-pass traversal | O(n)            | O(1)             |

Explanation

Intial Thoughts

To approach this problem, we first need to understand the operation allowed: swapping two adjacent elements with the same number of set bits. This means we should group elements based on the number of set bits. Then, we should consider how to sort each group and ensure the sorted groups can be combined in ascending order. We also need to identify conditions where sorting is impossible, such as when elements with fewer set bits are larger than those in previous groups.

Intuitive Analysis

Intuitively, the solution involves tracking the maximum and minimum values within each group of elements with the same number of set bits. By comparing these values across different groups, we can determine if the array can be sorted. If elements with fewer set bits are smaller than those in previous groups, it suggests the array can be sorted. However, if at any point an element with fewer set bits is larger than the maximum of the previous group, it indicates the array cannot be sorted in ascending order. This approach requires iterating through the array, checking the number of set bits in each element, and updating the maximum and minimum values accordingly.

1. Intuition

• The problem requires determining if an array can be sorted in ascending order by swapping adjacent elements with the same number of set bits.
• To approach this problem, we need to understand the concept of set bits and how it applies to the given array.
• We should consider the binary representation of each number and the number of set bits in each number.
• The key insight is to group numbers with the same number of set bits together and check if they can be sorted within their group.
• If the minimum value in a group is less than the maximum value in the previous group, it indicates that the array cannot be sorted.
• The solution involves iterating through the array and checking the number of set bits in each number to determine if it can be swapped with adjacent numbers.
• By maintaining the maximum and minimum values in each group, we can determine if the array can be sorted in ascending order.

2. Implementation

• The solution uses the __builtin_popcount function to count the number of set bits in each number.
• It initializes variables set_bits, curr_max, curr_min, and prev_max to keep track of the number of set bits and the maximum and minimum values in each group.
• The solution iterates through the array using a for loop, checking the number of set bits in each number and updating the curr_max and curr_min variables accordingly.
• If the number of set bits in the current number is different from the previous number, it updates the prev_max variable and resets the curr_max and curr_min variables.
• The solution checks if the curr_min value is less than the prev_max value to determine if the array can be sorted.
• If the array can be sorted, the solution returns true; otherwise, it returns false.
• The time complexity of the solution is O(n), where n is the length of the input array, and the space complexity is O(1) since it only uses a constant amount of space.

Complexity Analysis

Time Complexity:

• The algorithm performs a single-pass traversal through the input array nums, which contains n elements, resulting in a linear time complexity.
• The dominant operations are the __builtin_popcount function calls, max and min calculations, and conditional checks, all of which run in constant time O(1).
• Since the loop iterates n times, and each iteration has constant time complexity, the overall time complexity is O(n) = O(1) * n = n, which simplifies to O(n).

Space Complexity:

• The algorithm uses a constant amount of space to store variables like set_bits, curr_max, curr_min, and prev_max, regardless of the input size n.
• No additional data structures that scale with input size are used, so the space complexity is not affected by the size of the input array nums.
• The space used does not grow with the size of the input, resulting in a constant space complexity of O(1).

Footnote

This question is rated as Medium difficulty.

Hints

Split the array into segments. Each segment contains consecutive elements with the same number of set bits.

From left to right, the previous segment’s largest element should be smaller than the current segment’s smallest element.

Similar Questions: