Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 <= 1001 <= nums[i] <= 28Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Bit Manipulation
[8,4,2,30,15]
[1,2,3,4,5]
[3,16,8,4,2]
sort-integers-by-the-number-of-1-bits)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3011: Find if Array Can Be Sorted
class Solution {
public boolean canSortArray(int[] nums) {
int preMx = 0;
int i = 0, n = nums.length;
while (i < n) {
int cnt = Integer.bitCount(nums[i]);
int j = i + 1;
int mi = nums[i], mx = nums[i];
while (j < n && Integer.bitCount(nums[j]) == cnt) {
mi = Math.min(mi, nums[j]);
mx = Math.max(mx, nums[j]);
j++;
}
if (preMx > mi) {
return false;
}
preMx = mx;
i = j;
}
return true;
}
}
// Accepted solution for LeetCode #3011: Find if Array Can Be Sorted
func canSortArray(nums []int) bool {
preMx := 0
i, n := 0, len(nums)
for i < n {
cnt := bits.OnesCount(uint(nums[i]))
j := i + 1
mi, mx := nums[i], nums[i]
for j < n && bits.OnesCount(uint(nums[j])) == cnt {
mi = min(mi, nums[j])
mx = max(mx, nums[j])
j++
}
if preMx > mi {
return false
}
preMx = mx
i = j
}
return true
}
# Accepted solution for LeetCode #3011: Find if Array Can Be Sorted
class Solution:
def canSortArray(self, nums: List[int]) -> bool:
pre_mx = 0
i, n = 0, len(nums)
while i < n:
cnt = nums[i].bit_count()
j = i + 1
mi = mx = nums[i]
while j < n and nums[j].bit_count() == cnt:
mi = min(mi, nums[j])
mx = max(mx, nums[j])
j += 1
if pre_mx > mi:
return False
pre_mx = mx
i = j
return True
// Accepted solution for LeetCode #3011: Find if Array Can Be Sorted
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3011: Find if Array Can Be Sorted
// class Solution {
// public boolean canSortArray(int[] nums) {
// int preMx = 0;
// int i = 0, n = nums.length;
// while (i < n) {
// int cnt = Integer.bitCount(nums[i]);
// int j = i + 1;
// int mi = nums[i], mx = nums[i];
// while (j < n && Integer.bitCount(nums[j]) == cnt) {
// mi = Math.min(mi, nums[j]);
// mx = Math.max(mx, nums[j]);
// j++;
// }
// if (preMx > mi) {
// return false;
// }
// preMx = mx;
// i = j;
// }
// return true;
// }
// }
// Accepted solution for LeetCode #3011: Find if Array Can Be Sorted
function canSortArray(nums: number[]): boolean {
let preMx = 0;
const n = nums.length;
for (let i = 0; i < n; ) {
const cnt = bitCount(nums[i]);
let j = i + 1;
let [mi, mx] = [nums[i], nums[i]];
while (j < n && bitCount(nums[j]) === cnt) {
mi = Math.min(mi, nums[j]);
mx = Math.max(mx, nums[j]);
j++;
}
if (preMx > mi) {
return false;
}
preMx = mx;
i = j;
}
return true;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.