Problem of The Day: Longest Subarray With Maximum Bitwise AND

Problem Statement

Intuition

The problem asks for finding the longest subarray where all elements are equal to the maximum element in the array. The first intuition is to loop through the array, find where the maximum value starts and ends, and keep track of the longest contiguous subarray.

Approach

1. First, find the maximum value in the array.
2. Use two pointers (start and end) to iterate through the array and keep track of the start and end of subarrays that consist of the maximum value.
3. When the value at the current index (end) equals the maximum, start recording the length of the subarray.
4. Update the result with the maximum length of contiguous subarrays where all elements are equal to the maximum value.
5. Return the longest length at the end.

Complexity

• Time complexity: The time complexity is \(O(n)\) because we iterate through the list once to find the maximum value and another time to find the longest subarray.

• Space complexity: The space complexity is \(O(1)\) because no extra space is used except for a few variables.

Code

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        N = len(nums)
        start, end = 0, 0
        res = 0
        max_val = max(nums)
        while end < N:
            if nums[end] == max_val:
                start = end
                while end < N and nums[end] == max_val:
                    res = max(res, end - start + 1)
                    end += 1
            else:
                end += 1
        return res

Editorial

Approach: Longest consecutive sequence of the maximum value

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        max_val = ans = current_streak = 0
        for num in nums:
            if max_val < num:
                max_val = num
                ans = current_streak = 0

            if max_val == num:
                current_streak += 1
            else:
                current_streak = 0

            ans = max(ans, current_streak)
        return ans

• time: O(N)
• space: O(1)