Longest Subarray With Maximum Bitwise AND

Longest Subarray With Maximum Bitwise AND

What is this problem about?

The Longest Subarray With Maximum Bitwise AND provides an array of positive integers. You need to find the maximum possible bitwise AND result of any non-empty subarray, and then return the length of the longest subarray that achieves this maximum bitwise AND value.

Why is this asked in interviews?

This is a classic "Brainteaser" disguised as a Bit Manipulation problem. Interviewers ask it to test your fundamental understanding of the bitwise AND operator. It checks whether you can mathematically deduce that the bitwise AND of two different numbers is always less than or equal to the maximum of those two numbers. Once you realize this, a complex bitwise problem turns into a simple array traversal.

Algorithmic pattern used

This problem relies on a Greedy / Array Traversal pattern based on a mathematical property. Because the bitwise AND of a number X with anything else will never be greater than X, the maximum bitwise AND of any subarray will simply be the absolute maximum single integer present in the array. Therefore, the problem simplifies to: find the maximum element in the array, and then find the longest contiguous sequence of that maximum element.

Example explanation

Suppose the array is [1, 2, 3, 3, 2, 3].

1. First, we identify the maximum bitwise AND possible. Using the property mentioned, this is just the maximum number in the array, which is 3.
2. Now, we just need to find the longest contiguous block of 3s.

• At index 2: 3. Current streak = 1.
• At index 3: 3. Current streak = 2. Max streak = 2.
• At index 4: 2. Streak breaks, resets to 0.
• At index 5: 3. Current streak = 1. The maximum streak of the maximum number is 2.

Common mistakes candidates make

The most glaring mistake is writing a brute-force solution with nested loops to calculate the bitwise AND of every possible subarray ($O(N^2)$ time), which will inevitably result in a Time Limit Exceeded error. Another mistake is overthinking the bit manipulation and trying to maintain a sliding window of bits, completely missing the mathematical shortcut that ANDing decreases or maintains value.

Interview preparation tip

For the Longest Subarray With Maximum Bitwise AND interview question, internalize this rule: A & B <= max(A, B). Whenever an interview problem asks to maximize a bitwise AND across a sequence, it almost always revolves around isolating the largest numbers and preventing them from being ANDed with smaller numbers.