We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find if Array Can Be Sorted

Difficulty: Medium

Problem Description

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.

Key Insights

  • The sorting of the array is only possible through adjacent swaps.
  • Elements can only be swapped if they have the same number of set bits in their binary representation.
  • Group elements by their set bit counts; each group can be sorted independently.
  • If the sorted version of the original array matches the sorted version of each group, the answer is true.

Space and Time Complexity

Time Complexity: O(n log n) - for sorting the groups of numbers.
Space Complexity: O(n) - for storing the groups of numbers based on the count of set bits.

Solution

The approach involves the following steps:

  1. Count the number of set bits for each element in the array.
  2. Group the elements based on their set bit counts into a dictionary.
  3. Sort each group.
  4. Flatten the sorted groups back into a single list and compare it with the sorted version of the original array.
  5. If they match, return true; otherwise, return false.

Code Solutions

def count_set_bits(n):
    return bin(n).count('1')

def can_be_sorted(nums):
    from collections import defaultdict
    
    groups = defaultdict(list)
    
    # Group numbers by their number of set bits
    for num in nums:
        set_bits = count_set_bits(num)
        groups[set_bits].append(num)
    
    sorted_nums = sorted(nums)
    sorted_groups = []
    
    # Sort each group and flatten it into a single list
    for key in sorted(groups.keys()):
        sorted_groups.extend(sorted(groups[key]))
    
    # Compare the sorted version of the original array with the new sorted array
    return sorted_groups == sorted_nums
← Back to All Questions