NeetCode #877LC-2401MediumBit Manipulation
← Back to All Problems#877 · #2401 · Longest Nice Subarray(最长优雅子数组)
📌 Problem Statement & Constraints
A subarray is called nice if the bitwise AND of every pair of elements at different positions in it is 0. Return the length of the longest nice subarray. Constraints:
1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9.💡 Core Algorithmic Approaches
- The pairwise-AND-zero condition is equivalent to: no bit position is set in two different elements of the subarray.
- Equivalently, the OR of the window has no bit shared by two elements, and the OR equals the sum of the elements.
- Maintain a sliding window whose OR mask records all bits currently in use.
- When a new element collides with the mask, shrink from the left until the collision is gone, then add the element.
💻 Benchmark Python3 Implementation
class Solution:
def longestNiceSubarray(self, nums: List[int]) -> int:
left = 0
used = 0 # OR of every bit currently in the window
best = 0
for right, x in enumerate(nums):
while used & x: # a bit collides -> shrink the window
used ^= nums[left]
left += 1
used |= x
best = max(best, right - left + 1)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index enters and leaves the window once.
💾 Space Complexity
O(1): a mask and two indices.
⚠️ Interview Pitfalls & Follow-ups
- Checking every pair inside the window: O(n^2) and unnecessary; the OR mask captures all collisions at once.
- Using
used &= ~nums[left]to remove the left element: that clears bits other elements may still hold. Inside a nice window every bit is unique, which is exactly what makesused ^= nums[left]safe. - Adding the new element before shrinking: the collision must be resolved first, otherwise the window is never nice.
- Recomputing the window OR from scratch: O(n^2) in the worst case; the incremental mask keeps it linear.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.