2419. Longest Subarray With Maximum Bitwise And

Problem Statement in English

You’re given an array of integers nums. Your task is to find the length of the longest contiguous subarray where the bitwise AND of all elements equals the maximum bitwise AND that can be obtained from any subarray of nums.

Approach

The first thing you need to realize is that the maximum bitwise AND of any subarray is the maximum element in that subarray.

So all we need to do is find the maximum element in nums and then find the longest contiguous subarray that consists of only this maximum element.

Solution in Python

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        target = max(nums)

        l = 0
        res = 0

        for r in range(len(nums)):
            if nums[r] == target:
                while nums[l] != nums[r]:
                    l += 1
                res = max(res, r - l + 1)
            else:
                l = r

        return res

Complexity

• Time: $O(n)$
  Since we are iterating through the array once.

• Space: $O(1)$
  Since we are using a constant amount of space for variables.

Mistakes I Made

I needed a hint to realize that the maximum bitwise AND of any subarray is simply the maximum element in that subarray. Once I understood that, the problem became straightforward.

And we are done.