Longest Nice Subarray

Problem Description

You are given an array nums consisting of positive integers. We call a subarray of nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0. Return the length of the longest nice subarray. A subarray is a contiguous part of an array. Note that subarrays of length 1 are always considered nice.

Key Insights

• A subarray is nice if for every pair of its elements, their bitwise AND equals 0.
• The bitwise AND of two numbers is 0 if they do not share any common bits (i.e., they are in different bit positions).
• We can use a sliding window technique to find the longest nice subarray efficiently.
• We need to keep track of the numbers in the current window and ensure that adding a new number does not violate the nice condition.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can employ the sliding window technique along with a bitmask to track the bits used by numbers in the current window. As we iterate through the array, we maintain a window of numbers that satisfy the nice condition. If a new number cannot be added without violating the condition, we adjust the window.

1. Initialize two pointers for the sliding window.
2. Use a variable to track the current bitmask representing the bits of numbers in the window.
3. Iterate through the array, updating the window and bitmask accordingly.
4. Whenever a number is added that conflicts with the current bitmask, move the left pointer to shrink the window until the condition is satisfied again.
5. Keep track of the maximum length of the nice subarray found during the iteration.

Code Solutions