Longest Subarray With Maximum Bitwise AND

Medium
725.

Longest Subarray With Maximum Bitwise AND

Longest Subarray With Maximum Bitwise AND is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarrayAnd = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Longest Subarray With Maximum Bitwise AND

  1. Hint 1

    ANDing more numbers can never increase the result — each extra operand can only clear bits.

  2. Hint 2

    So the largest possible AND is the array's maximum element, achieved by a subarray of equal maxima.

  3. 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

  1. Find the maximum value m in nums.
  2. Scan for the longest run of consecutive elements equal to m.
  3. 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

Java

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