Skip to content

3011. Find if Array Can Be Sorted 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  bool canSortArray(vector<int>& nums) {
    // Divide the array into distinct segments where each segment is comprised
    // of consecutive elements sharing an equal number of set bits. Ensure that
    // for each segment, when moving from left to right, the maximum of a
    // preceding segment is less than the minimum of the following segment.
    int prevSetBits = 0;
    int prevMax = INT_MIN;  // the maximum of the previous segment
    int currMax = INT_MIN;  // the maximum of the current segment
    int currMin = INT_MAX;  // the minimum of the current segment

    for (const int num : nums) {
      const int setBits = __builtin_popcount(num);
      if (setBits != prevSetBits) {  // Start a new segment.
        if (prevMax > currMin)
          return false;
        prevSetBits = setBits;
        prevMax = currMax;
        currMax = num;
        currMin = num;
      } else {  // Continue with the current segment.
        currMax = max(currMax, num);
        currMin = min(currMin, num);
      }
    }

    return prevMax <= currMin;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public boolean canSortArray(int[] nums) {
    // Divide the array into distinct segments where each segment is comprised
    // of consecutive elements sharing an equal number of set bits. Ensure that
    // for each segment, when moving from left to right, the maximum of a
    // preceding segment is less than the minimum of the following segment.
    int prevSetBits = 0;
    int prevMax = Integer.MIN_VALUE; // the maximum of the previous segment
    int currMax = Integer.MIN_VALUE; // the maximum of the current segment
    int currMin = Integer.MAX_VALUE; // the minimum of the current segment

    for (final int num : nums) {
      final int setBits = Integer.bitCount(num);
      if (setBits != prevSetBits) { // Start a new segment.
        if (prevMax > currMin)
          return false;
        prevSetBits = setBits;
        prevMax = currMax;
        currMax = num;
        currMin = num;
      } else { // Continue with the current segment.
        currMax = Math.max(currMax, num);
        currMin = Math.min(currMin, num);
      }
    }

    return prevMax <= currMin;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def canSortArray(self, nums: list[int]) -> int:
    # Divide the array into distinct segments where each segment is comprised
    # of consecutive elements sharing an equal number of set bits. Ensure that
    # for each segment, when moving from left to right, the maximum of a
    # preceding segment is less than the minimum of the following segment.
    prevSetBits = 0
    prevMax = -math.inf  # the maximum of the previous segment
    currMax = -math.inf  # the maximum of the current segment
    currMin = math.inf   # the minimum of the current segment

    for num in nums:
      setBits = num.bit_count()
      if setBits != prevSetBits:  # Start a new segment.
        if prevMax > currMin:
          return False
        prevSetBits = setBits
        prevMax = currMax
        currMax = num
        currMin = num
      else:  # Continue with the current segment.
        currMax = max(currMax, num)
        currMin = min(currMin, num)

    return prevMax <= currMin