Skip to content

Find if Array Can Be Sorted⚓︎

Link

Solution⚓︎

See reference (Chinese).

Way 1⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ) {
            int start = i;
            int ones = __builtin_popcount(nums[i++]);
            while (i < n && __builtin_popcount(nums[i]) == ones) i++;
            sort(nums.begin() + start, nums.begin() + i);
        }
        return is_sorted(nums.begin(), nums.end());
    }
};
  • Time complexity: \(O(n\log n)\);
  • Space complexity: \(O(1)\).

Way 2⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        int n = nums.size(), i = 0, preMax = 0;
        while (i < n) {
            int mx = nums[i];
            int ones = __builtin_popcount(mx);
            while (i < n && __builtin_popcount(nums[i]) == ones) {
                if (nums[i] < preMax) return false;
                mx = max(mx, nums[i++]);
            }
            preMax = mx;
        }
        return true;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).