Longest Subarray With Maximum Bitwise AND — Solution
Longest Subarray With Maximum Bitwise AND solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Longest Subarray With Maximum Bitwise AND is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Brainteaser
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Among all subarrays of nums, consider those whose bitwise AND is as large as possible.
Return the length of the longest such subarray.
Example 1
Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation: The largest achievable AND is 3, reached only by the run [3,3].
Example 2
Input: nums = [1,2,3,4]
Output: 1
Explanation: The maximum AND is 4, from the single element.
Example 3
Input: nums = [5,5,5]
Output: 3
Constraints
1 <= nums.length <= 1000001 <= nums[i] <= 1000000
Hints for Longest Subarray With Maximum Bitwise AND
Hint 1
ANDing more numbers can never increase the result — each extra operand can only clear bits.
Hint 2
So the largest possible AND is the array's maximum element, achieved by a subarray of equal maxima.
Hint 3
The answer is the longest run of the maximum value.
How to solve Longest Subarray With Maximum Bitwise AND
Bitwise AND is monotone downward: a & b <= min(a, b). So no subarray can beat the single largest element, and a subarray achieves that value only if every element equals it.
Approach
- Find the maximum value
minnums. - Scan for the longest run of consecutive elements equal to
m. - Return that run length.
Why it works
For any subarray, its AND is at most its minimum, which is at most the global maximum — so the best achievable value is m. A subarray whose AND equals m must have every element at least m bitwise, and since m is the maximum, every element must equal m exactly.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Trying to compute ANDs over sliding windows is both slow and unnecessary.
- Counting all occurrences of the maximum rather than the longest consecutive run overcounts.
Reference solution
Python
from typing import List
def longestSubarrayAnd(nums: List[int]) -> int:
best = max(nums)
run = longest = 0
for x in nums:
run = run + 1 if x == best else 0
longest = max(longest, run)
return longestJava
public static int longestSubarrayAnd(int[] nums) {
int best = nums[0];
for (int x : nums) best = Math.max(best, x);
int run = 0, longest = 0;
for (int x : nums) {
run = x == best ? run + 1 : 0;
longest = Math.max(longest, run);
}
return longest;
}C++
int longestSubarrayAnd(vector<int>& nums) {
int best = *max_element(nums.begin(), nums.end());
int run = 0, longest = 0;
for (int x : nums) {
run = x == best ? run + 1 : 0;
longest = max(longest, run);
}
return longest;
}JavaScript
var longestSubarrayAnd = function(nums) {
var best = nums[0];
for (var i = 1; i < nums.length; i++) {
if (nums[i] > best) best = nums[i];
}
var run = 0, longest = 0;
for (var j = 0; j < nums.length; j++) {
run = nums[j] === best ? run + 1 : 0;
if (run > longest) longest = run;
}
return longest;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation