Find if Array Can Be Sorted

MediumArrayBit ManipulationSorting

Solution

export function canSortArray(nums: number[]): boolean {
  const n = nums.length;
 
  let bitCount = countBit(nums[0]);
  let [maxValue, minValue] = [nums[0], nums[0]];
  let prevMaxValue = Number.MIN_SAFE_INTEGER;
 
  for (let i = 1; i < n; i++) {
    if (countBit(nums[i]) === bitCount) {
      maxValue = Math.max(maxValue, nums[i]);
      minValue = Math.min(minValue, nums[i]);
    } else {
      if (minValue < prevMaxValue) {
        return false;
      }
      prevMaxValue = maxValue;
      bitCount = countBit(nums[i]);
      [maxValue, minValue] = [nums[i], nums[i]];
    }
  }
  return prevMaxValue <= minValue;
}
 
function countBit(num: number) {
  let result = 0;
  let curr = num;
  while (0 < curr) {
    result += curr & 1;
    curr = curr >> 1;
  }
  return result;
}

Complexity

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