Longest Subarray With Maximum Bitwise AND — Medium Problem & Solution

Among all subarrays of nums, consider those whose bitwise AND is as large as possible. Return the length of the longest such subarray.

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 <= 100000
1 <= nums[i] <= 1000000

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 m in nums.
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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue