Problem of The Day: Find if Array Can Be Sorted

Problem Statement

Intuition

The problem requires checking if an array can be sorted by dividing it into segments based on certain criteria. Our initial thought is to divide the array into segments where each segment contains numbers with the same number of set bits (1s) in their binary representation. By sorting within these segments, we can achieve an overall sorted array if each segment’s maximum value is smaller than the next segment’s minimum value.

Approach

1. Initial Check: First, iterate through the array to check if it is already sorted. If so, return True.
2. Segment Creation: If the array is not sorted, split it into segments where each segment contains numbers with the same number of set bits in their binary representation. To determine the number of set bits, we use the helper function get_set_bit_from.
3. Segment Boundaries: For each segment, record the maximum and minimum values, which will help us determine if the entire array can be sorted by comparing adjacent segments.
4. Final Check: After forming segments, iterate through the segment boundaries. If any segment’s maximum value is greater than the next segment’s minimum value, return False. If no such case is found, return True.

Helper Function

• get_set_bit_from(num): This function calculates the number of set bits (1s) in the binary representation of a number, which we use to group numbers into segments.

Complexity

• Time Complexity:

  • Initial check: \(O(N)\)
  • Segment creation: \(O(N)\)
  • Final check: \(O(S)\), where ( S ) is the number of segments (in the worst case, ( S \approx N )).
  • Overall complexity: \(O(N)\).

• Space Complexity:

  • \(O(S)\) for storing segment boundaries, where ( S ) is the number of segments.

Code

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        N = len(nums)
        # Check if array is already sorted
        for i in range(N - 1):
            if nums[i] > nums[i + 1]:
                break
        else:
            return True

        # Create segments based on set bits
        curr_segment = []
        curr_set_bit = 0
        res = []
        for num in nums:
            set_bit = self.get_set_bit_from(num)
            if curr_set_bit != set_bit:
                if curr_segment:
                    res.append([max(curr_segment), min(curr_segment)])
                curr_segment = []
                curr_set_bit = set_bit
            curr_segment.append(num)

        res.append([max(curr_segment), min(curr_segment)])

        # Check if segments are in sorted order
        for i in range(len(res) - 1):
            prev_max, _ = res[i]
            _, curr_min = res[i + 1]
            if prev_max > curr_min:
                return False

        return True

    def get_set_bit_from(self, num):
        ones = 0
        while num > 0:
            ones += 1
            num = num & (num - 1)
        return ones

Editorial

Approach 1: Bubble Sort

class Solution:
    def canSortArray(self, nums):
        n = len(nums)

        # Avoid modifying the input directly
        # Create a copy of the input array
        values = nums.copy()

        for i in range(n):
            for j in range(n - i - 1):
                if values[j] <= values[j + 1]:
                    # No swap needed
                    continue
                else:
                    if bin(values[j]).count("1") == bin(values[j + 1]).count(
                        "1"
                    ):
                        # Swap the elements
                        values[j], values[j + 1] = values[j + 1], values[j]
                    else:
                        return False
        return True

• time: O(n^2)
• space: O(n)

Approach 2: Sortable Segments

class Solution:
    def canSortArray(self, nums):
        # Number of set bits of the elements in the current segment
        num_of_set_bits = bin(nums[0]).count("1")
        max_of_segment = nums[0]
        min_of_segment = nums[0]

        # Initialize max of the previous segment to the smallest possible integer
        max_of_prev_segment = float("-inf")

        for i in range(1, len(nums)):
            if bin(nums[i]).count("1") == num_of_set_bits:
                # Element belongs to the same segment
                # Update min and max values of the segment
                max_of_segment = max(max_of_segment, nums[i])
                min_of_segment = min(min_of_segment, nums[i])
            else:  # Element belongs to a new segment
                # Check if the segments are arranged properly
                if min_of_segment < max_of_prev_segment:
                    return False

                # Update the previous segment's max
                max_of_prev_segment = max_of_segment

                # Start a new segment with the current element
                max_of_segment = nums[i]
                min_of_segment = nums[i]
                num_of_set_bits = bin(nums[i]).count("1")

        # Final check for proper segment arrangement
        if min_of_segment < max_of_prev_segment:
            return False

        return True

• time: O(n)
• space: O(1)

Approach 3: Forward and Backward Pass

class Solution:
    def canSortArray(self, nums):
        n = len(nums)
        values = nums.copy()  # Create a copy of the original array

        # First Pass: Iterate from left to right
        # Goal: Move the maximum value of each segment as far right as possible
        for i in range(n - 1):
            if values[i] <= values[i + 1]:
                continue
            else:
                # Check if the current and next element have the same number of set bits
                if bin(values[i]).count("1") == bin(values[i + 1]).count("1"):
                    # Swap if they do
                    temp = values[i]
                    values[i] = values[i + 1]
                    values[i + 1] = temp
                else:
                    return False  # Return false if they cannot be swapped

        # Second Pass: Iterate from right to left
        # Goal: Move the minimum value of each segment as far left as possible
        for i in range(n - 1, 0, -1):
            if values[i] >= values[i - 1]:
                continue
            else:
                # Check if the current and previous element have the same number of set bits
                if bin(values[i]).count("1") == bin(values[i - 1]).count("1"):
                    # Swap if they do
                    temp = values[i]
                    values[i] = values[i - 1]
                    values[i - 1] = temp
                else:
                    return False  # Return false if they cannot be swapped

        # If both passes complete without returning false, the array can be sorted
        return True

• time: O(n)
• space: O(n)