Longest Nice Subarray — LeetCode 2401 Python Solution

The problem

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.

Example

Input

nums = [1,3,8,48,10]

Output

3

Explanation

The longest nice subarray is [3,8,48]. This subarray satisfies the conditions:

Python solution

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        ans = mask = l = 0
        for r, x in enumerate(nums):
            while mask & x:
                mask ^= nums[l]
                l += 1
            mask |= x
            ans = max(ans, r - l + 1)
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2401. Longest Nice Subarray is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems