⚡Flashcard Drill➔
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

  1. The pairwise-AND-zero condition is equivalent to: no bit position is set in two different elements of the subarray.
  2. Equivalently, the OR of the window has no bit shared by two elements, and the OR equals the sum of the elements.
  3. Maintain a sliding window whose OR mask records all bits currently in use.
  4. 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 makes used ^= 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.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems