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:
- Space: