NeetCode #875LC-3011MediumBit Manipulation
← Back to All Problems#875 · #3011 · Find if Array Can Be Sorted(判断一个数组是否可以变为有序)
📌 Problem Statement & Constraints
Given an array
nums of positive integers, you may swap two adjacent elements only if they have the same number of set bits. Return whether the array can be sorted using any number of such swaps. Constraints: 1 <= nums.length <= 100, 1 <= nums[i] <= 2^8.💡 Core Algorithmic Approaches
- Adjacent swaps are allowed only between elements of equal popcount, so two elements with different popcounts can never cross each other.
- The array therefore splits into maximal contiguous runs of equal popcount, and each run can be permuted arbitrarily.
- Sorting each run in place is the best that can be achieved.
- If the resulting array is globally sorted, the answer is true; otherwise the run boundaries block a full sort.
💻 Benchmark Python3 Implementation
class Solution:
def canSortArray(self, nums: List[int]) -> bool:
n = len(nums)
def popcount(x: int) -> int:
return bin(x).count("1")
i = 0
while i < n:
j = i
# extend the run while the popcount stays the same
while j + 1 < n and popcount(nums[j + 1]) == popcount(nums[i]):
j += 1
nums[i:j + 1] = sorted(nums[i:j + 1])
i = j + 1
return nums == sorted(nums)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): sorting the runs dominates.
💾 Space Complexity
O(n): the slices produced by the sort.
⚠️ Interview Pitfalls & Follow-ups
- Sorting the whole array immediately: that ignores the restriction, since elements with different popcounts can never cross.
- Grouping by popcount value globally: two equal-popcount elements separated by a different-popcount element can never meet, so the runs must be contiguous.
- Assuming any two same-popcount elements can swap: only adjacent swaps are allowed, but within a contiguous run they generate every permutation.
- Returning true as soon as each run is sorted: the global check
nums == sorted(nums)is the actual requirement.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.