Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For nonnegative values, bitwise AND cannot exceed any participating value. A singleton containing the array maximum already attains the greatest possible AND. To retain that same maximum in a longer subarray, every element must equal it.

Approach

Find the largest array value. Scan again, increasing a run counter whenever the current value equals that maximum and resetting it otherwise. Track and return the longest run. ANDing a run of identical maximum values preserves the value, while including any smaller element would force the AND below it. Thus only the lengths of maximum-valued runs matter.

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        MX = max(nums)
        curr = 0
        res = 0

        for i in range(n):
            if nums[i] == MX:
                curr += 1
            else:
                curr = 0
            res = max(res, curr)

        return res

Complexity analysis

Let n = nums.length. Both displayed implementations scan once to find the maximum and once to find its longest consecutive run, taking O(n) time and O(1) auxiliary space.