2419. Longest Subarray With Maximum Bitwise AND

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

• In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
The maximum possible bitwise AND of a subarray is 3.
The longest subarray with that value is [3,3], so we return 2.

Example 2:

Input: nums = [1,2,3,4]
Output: 1
Explanation:
The maximum possible bitwise AND of a subarray is 4.
The longest subarray with that value is [4], so we return 1.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106

Approach 01:

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int maxLength = 0; // To store the maximum length of subarray
        int maxElementIndex = 0; // To track the index of the maximum element found
        int currentStreakLength = 0; // Length of the current streak of the maximum element

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == nums[maxElementIndex]) {
                maxLength = max(maxLength, ++currentStreakLength); // Update the max length
            } else if (nums[i] > nums[maxElementIndex]) {
                maxElementIndex = i; // Update the index of the new maximum element
                currentStreakLength = 1; // Reset the streak length to 1 for the new element
                maxLength = 1; // Reset the max length to 1
            } else {
                currentStreakLength = 0; // Reset the streak length if element is less than max
            }
        }

        return maxLength;
    }
};

class Solution:
    def longestSubarray(self, nums):
        maxLength = 0  # To store the maximum length of subarray
        maxElementIndex = 0  # To track the index of the maximum element found
        currentStreakLength = 0  # Length of the current streak of the maximum element

        for i in range(len(nums)):
            if nums[i] == nums[maxElementIndex]:
                currentStreakLength += 1
                maxLength = max(maxLength, currentStreakLength)  # Update the max length
            elif nums[i] > nums[maxElementIndex]:
                maxElementIndex = i  # Update the index of the new maximum element
                currentStreakLength = 1  # Reset the streak length to 1 for the new element
                maxLength = 1  # Reset the max length to 1
            else:
                currentStreakLength = 0  # Reset the streak length if element is less than max

        return maxLength

Time Complexity

• Iterating Through the Array:

  The algorithm makes a single pass through the input array to find the longest subarray of the maximum element. Since each element is visited once, the time complexity is \(O(n)\), where n is the size of the input array.

• Updating Maximum Element and Streak:

  Each comparison and update (for the maximum element and streak length) happens in constant time, i.e., \(O(1)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the size of the input array.

Space Complexity

• Space for Variables:

  Only a few integer variables are used to track the current streak, maximum element, and the length of the longest subarray. This requires \(O(1)\) extra space.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as the algorithm uses a constant amount of extra space regardless of the input size.