LeetCode 2419: Longest Subarray With Maximum Bitwise AND

All subarrays

For each subarray we can compute the Bitwise AND in $\mathcal{O}(1)$ time.

Time $\mathcal{O}(n^2)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        max_and = 0
        max_len = 0
        for i in range(len(nums)):
            if nums[i] > max_and:
                max_and = nums[i]
                max_len = 1
            elif nums[i] == max_and:
                max_len = max(max_len, 1)
            
            bitwise_and = nums[i]
            for j in range(i+1, len(nums)):
                bitwise_and &= nums[j]
                if bitwise_and > max_and:
                    max_and = bitwise_and
                    max_len = j-i+1
                elif bitwise_and == max_and:
                    max_len = max(max_len, j-i+1)
                    
        return max_len

Property of AND

Note, all numbers are positive. We can never increase a positive number $x$ by Bitwise ANDing with another number $y$ , the best we can do is to keep $x$ as it is and that happens when we have: $(x \texttt{ and } x)$ . So, the maximum Bitwise AND is the maximum number in nums. From that point of view, we need to find the longest contiguous sequence of the maximum number. We use sliding window.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        max_len = 0
        max_num = float("-inf")
        begin = 0
        for end, x in enumerate(nums):
            if x > max_num:
                max_num = x
                begin = end
                max_len = 1
                continue

            if x < max_num:
                max_len = max(max_len, end-begin)
                begin = end+1
        
        # Since the last begin, all numbers might have been
        # max, so we include that stretch.
        return max(max_len, len(nums)-begin)

unreasonably effective