Problem Description

You have an array nums containing positive integers.

A subarray is called nice if for every pair of elements at different positions in the subarray, their bitwise AND equals 0.

Your task is to find the length of the longest nice subarray.

Key points to understand:

• A subarray must be contiguous (consecutive elements from the original array)
• For a subarray to be nice, ANY two elements from different positions must have bitwise AND = 0
• A subarray of length 1 is always considered nice (since there are no pairs to check)

For example, if we have elements a, b, and c in a subarray, for it to be nice:

• a & b = 0
• a & c = 0
• b & c = 0

This means that for any bit position, at most one element in the nice subarray can have a 1 at that position. If two or more elements have a 1 at the same bit position, their bitwise AND would not be 0.

The solution uses a sliding window approach with two pointers. It maintains a mask variable that tracks the bitwise OR of all elements in the current window. When adding a new element x, if mask & x != 0, it means x shares some bit positions with existing elements in the window, so we need to shrink the window from the left until no bits overlap. The mask is updated by XORing out elements when removing them from the left, and ORing in new elements when adding them from the right.

Intuition

The key insight is understanding what makes a subarray "nice". For any two numbers to have a bitwise AND of 0, they cannot share any 1 bits at the same position.

Think about it this way: if number a has a 1 at bit position 3, and number b also has a 1 at bit position 3, then a & b will have a 1 at position 3, making it non-zero. So for a subarray to be nice, each bit position can have at most one number with a 1 at that position.

This observation leads us to a crucial realization: we can track all the "occupied" bit positions in our current subarray using a single variable. If we OR all numbers in our subarray together, the result tells us exactly which bit positions are currently occupied by at least one 1.

For example, if we have [5, 2] where 5 = 101 and 2 = 010 in binary, their OR gives us 111, showing that bit positions 0, 1, and 2 are occupied.

Now, when we try to add a new number to our subarray, we can quickly check if it conflicts with existing numbers by doing mask & new_number. If this result is non-zero, it means the new number has 1s at positions that are already occupied - a conflict!

This naturally suggests a sliding window approach:

1. Expand the window by adding elements from the right
2. If a new element conflicts with the current window (shares bit positions), shrink from the left until there's no conflict
3. Keep track of the maximum window size achieved

The beauty of using OR for the mask is that when we remove an element from the left, we can update the mask by XORing it out (since we know that element's bits were unique in the window). When adding to the right, we OR it in to mark its bit positions as occupied.

Learn more about Sliding Window patterns.

Solution Approach

The solution uses a two-pointer sliding window technique with bit manipulation to efficiently find the longest nice subarray.

Variables Used:

• l and r: Left and right pointers defining our sliding window
• mask: Tracks all occupied bit positions in the current window using bitwise OR
• ans: Stores the maximum window size found so far

Algorithm Steps:

1. Initialize variables: Start with ans = mask = l = 0. The right pointer r will be controlled by the enumerate function.

2. Expand window from right: For each element x at position r:

   • Check if mask & x is non-zero (conflict exists)

3. Shrink window from left when needed:

   while mask & x:
       mask ^= nums[l]
       l += 1

   • If mask & x != 0, the new element shares bit positions with existing elements
   • Remove elements from the left by XORing them out of the mask: mask ^= nums[l]
   • Move left pointer forward: l += 1
   • Continue until no conflict exists (mask & x == 0)

4. Add new element to window:

   mask |= x

   • OR the new element into the mask to mark its bit positions as occupied

5. Update maximum length:

   ans = max(ans, r - l + 1)

   • Calculate current window size as r - l + 1
   • Keep track of the maximum size seen

Why XOR for removal and OR for addition?

• When adding: mask |= x sets all bits that are 1 in x to 1 in the mask
• When removing: mask ^= nums[l] flips the bits of nums[l] in the mask. Since we know nums[l]'s bits are unique in the window (no overlap with other elements), XORing effectively removes only its bits from the mask

Time Complexity: O(n) where n is the length of the array. Each element is visited at most twice (once by right pointer, once by left pointer).

Space Complexity: O(1) as we only use a constant amount of extra variables.

Example Walkthrough

Let's walk through the solution with nums = [5, 2, 8, 1]

In binary:

• 5 = 101
• 2 = 010
• 8 = 1000
• 1 = 001

Initial state: l = 0, mask = 0, ans = 0

Step 1: r = 0, x = 5 (binary: 101)

• Check: mask & 5 = 0 & 101 = 0 (no conflict)
• Add to window: mask = 0 | 101 = 101
• Update answer: ans = max(0, 0-0+1) = 1
• Window: [5], mask shows bits 0 and 2 are occupied

Step 2: r = 1, x = 2 (binary: 010)

• Check: mask & 2 = 101 & 010 = 0 (no conflict)
• Add to window: mask = 101 | 010 = 111
• Update answer: ans = max(1, 1-0+1) = 2
• Window: [5, 2], mask shows bits 0, 1, and 2 are occupied

Step 3: r = 2, x = 8 (binary: 1000)

• Check: mask & 8 = 111 & 1000 = 0 (no conflict)
• Add to window: mask = 111 | 1000 = 1111
• Update answer: ans = max(2, 2-0+1) = 3
• Window: [5, 2, 8], mask shows bits 0, 1, 2, and 3 are occupied

Step 4: r = 3, x = 1 (binary: 001)

• Check: mask & 1 = 1111 & 001 = 1 (conflict! bit 0 is shared)
• Shrink window:
  • Remove nums[0] = 5: mask = 1111 ^ 101 = 1010
  • Move left: l = 1
  • Check again: mask & 1 = 1010 & 001 = 0 (no more conflict)
• Add to window: mask = 1010 | 001 = 1011
• Update answer: ans = max(3, 3-1+1) = 3
• Window: [2, 8, 1]

Final answer: 3 (the longest nice subarray is [5, 2, 8] with length 3)

Notice how when we encountered 1, it conflicted with 5 (both have bit 0 set). By removing 5 from the left, we resolved the conflict and could include 1 in our window.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers (l and r). The right pointer r iterates through each element in the array exactly once via the enumerate(nums) loop. While there is an inner while loop that moves the left pointer l, each element can only be added to and removed from the window once. Specifically, each element enters the window when r reaches it (via mask |= x) and exits at most once when l passes it (via mask ^= nums[l]). Since each of the n elements is processed at most twice (once when entering and once when leaving the window), the total number of operations is bounded by 2n, giving us a time complexity of O(n), where n is the length of the array nums.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The variables ans, mask, l, r, and x are all single integers that don't scale with the input size. The mask variable stores a bitwise OR of the current window elements, but since it's just a single integer (not an array or data structure that grows with input), it requires O(1) space regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bit Removal Using OR Instead of XOR

A common mistake is trying to remove elements from the bit mask using subtraction or OR operations instead of XOR.

Incorrect approach:

while mask & x:
    mask -= nums[l]  # Wrong! Arithmetic subtraction doesn't work for bit removal
    # OR
    mask |= ~nums[l]  # Wrong! This sets unwanted bits
    l += 1

Why this fails:

• Arithmetic subtraction doesn't properly remove individual bits from a bitmask
• Using OR with complement sets all bits except those in nums[l], corrupting the mask

Correct approach:

while mask & x:
    mask ^= nums[l]  # Correct! XOR flips the bits, effectively removing them
    l += 1

2. Misunderstanding the "Nice" Condition

Some might think checking adjacent elements is sufficient, but the condition requires ALL pairs in the subarray to have AND = 0.

Incorrect understanding:

# Wrong! Only checking consecutive elements
for i in range(len(nums) - 1):
    if nums[i] & nums[i+1] == 0:
        # extend subarray

Correct understanding: Every element in the nice subarray must have completely disjoint bit positions from every other element. The mask tracks ALL occupied bit positions across the entire window.

3. Off-by-One Error in Length Calculation

Common mistake:

ans = max(ans, r - l)  # Wrong! Missing the +1

Correct calculation:

ans = max(ans, r - l + 1)  # Correct! Inclusive count

The length should be right - left + 1 because both endpoints are inclusive. For example, a subarray from index 2 to 4 has length 3 (indices 2, 3, 4), not 2.

4. Not Handling Single Elements

Forgetting that a single element always forms a nice subarray.

Incomplete solution:

if len(nums) == 1:
    return 1  # Unnecessary special case

The sliding window approach naturally handles this - when the window contains just one element, r - l + 1 = 1, which is correct.