You are given an integer array nums of size n.
Consider a non-empty subarray from nums that has the maximum possible bitwise AND.
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 <= 1051 <= nums[i] <= 106This approach involves finding the maximum element in the array since it would potentially be the maximum bitwise AND when considered individually or consecutively. Then, we scan through the array to find the longest subarray containing only this element.
The code finds the maximum element in the array and then iterates through the array to find the longest contiguous subarray of this maximum element. If a new maximum element is found, it resets the count.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because we iterate through the array once.
Space Complexity: O(1) as no extra space is used apart from variables.
This approach involves using a sliding window to determine the longest subarray where the bitwise AND remains at its maximum value. Begin from the end of the array since the maximum AND value after considering all elements is often the last element itself or a combination found traversing backward.
Initially, the maximum AND is assumed to be the last element. A reverse scan utilizing a sliding window calculates the longest subarray conforming to this value.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as it involves a single backward traversal.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Finding Maximum Element | Time Complexity: O(n) because we iterate through the array once. Space Complexity: O(1) as no extra space is used apart from variables. |
| Sliding Window for Maximum AND Subarray | Time Complexity: O(n), as it involves a single backward traversal. Space Complexity: O(1). |
Longest Subarray With Maximum Bitwise AND - Leetcode 2419 - Python • NeetCodeIO • 6,508 views views
Watch 9 more video solutions →Practice Longest Subarray With Maximum Bitwise AND with our built-in code editor and test cases.
Practice on FleetCode