Longest Subarray With Maximum Bitwise AND - Solution & Explanation

Problem Overview: Given an integer array nums, return the length of the longest contiguous subarray whose bitwise AND value is as large as possible. The trick is realizing what the maximum possible AND value of any subarray can actually be.

The bitwise AND of multiple numbers can never exceed the largest number in the array. In practice, adding more elements to an AND operation usually decreases the value because bits drop to 0 whenever any number has that bit unset. That observation drives the optimal solution.

Approach 1: Finding Maximum Element (O(n) time, O(1) space)

The maximum bitwise AND obtainable from any subarray is simply the maximum value in nums. Any AND involving a smaller number clears at least one bit, producing a result smaller than that maximum. Because of this, the only way to achieve the maximum AND value is to take subarrays where every element equals the maximum number.

The algorithm is straightforward: first compute max_val = max(nums). Then iterate through the array and count consecutive elements equal to max_val. Track the longest streak. Each streak represents a subarray whose AND equals max_val. This single pass produces the answer in linear time.

This solution relies on properties of bit manipulation. Since AND operations only remove bits, the maximum achievable result must already exist as an element in the array. The rest of the problem reduces to a simple scan over an array.

Approach 2: Sliding Window for Maximum AND Subarray (O(n) time, O(1) space)

You can also think about the problem using a sliding window. First determine the global maximum value in the array. Then expand a window while elements remain equal to that maximum. The moment a smaller value appears, the window must reset because including that element would drop the AND result below the maximum.

The window effectively tracks runs of the maximum element. Maintain two pointers or simply a running length of the current window. When nums[i] == max_val, extend the window. Otherwise reset it to zero. Record the largest window size encountered during the scan.

This framing is useful if you are practicing sliding window patterns. Conceptually, the window represents the longest valid segment where the AND result remains equal to the maximum possible value.

Recommended for interviews: Interviewers usually expect the maximum-element insight. A brute force approach that computes AND for every subarray quickly becomes O(n^2) or worse. Recognizing the bitwise property that the AND cannot exceed the maximum element leads directly to the optimal O(n) scan. Demonstrating that reasoning shows strong understanding of both bit manipulation behavior and efficient array traversal.