3011. Find if Array Can Be Sorted LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3011. Find if Array Can Be Sorted LeetCode Solution with the best time and space complexity. The solution to Find if Array Can Be Sorted problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find if Array Can Be Sorted solution in C++
Find if Array Can Be Sorted solution in Java
Find if Array Can Be Sorted solution in Python
Additional Resources

3011. Find if Array Can Be Sorted LeetCode Solution image

Problem Statement of Find if Array Can Be Sorted

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

3011. Find if Array Can Be Sorted LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

3011. Find if Array Can Be Sorted LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

3011. Find if Array Can Be Sorted LeetCode Solution in Python

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
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents