Longest Subarray With Maximum Bitwise AND

medium bit manipulation array brainteaser

Problem

Let k be the maximum bitwise AND over every non-empty subarray of nums. Among all subarrays whose bitwise AND equals k, return the length of the longest one.

Key observation: ANDing two different values can only turn bits off, so a & b < max(a, b) whenever a ≠ b. Hence the best possible AND is simply k = max(nums), achieved by a single element. The answer is the longest run of consecutive elements all equal to max(nums).

Inputnums = [1, 2, 3, 3, 2, 2]

Output2

The maximum AND is 3. The longest run of 3's is [3, 3], so the answer is 2.

nums (comma-separated, 1..10⁶)

def longestSubarray(nums):
    mx = max(nums)        # best AND equals the largest element
    best = 0              # longest valid run so far
    cur = 0               # length of current run of mx
    for v in nums:
        if v == mx:
            cur += 1
            best = max(best, cur)
        else:
            cur = 0       # run broken, reset
    return best

function longestSubarray(nums) {
  const mx = Math.max(...nums); // best AND equals the largest element
  let best = 0;                 // longest valid run so far
  let cur = 0;                  // length of current run of mx
  for (const v of nums) {
    if (v === mx) {
      cur += 1;
      best = Math.max(best, cur);
    } else {
      cur = 0;                  // run broken, reset
    }
  }
  return best;
}

int longestSubarray(int[] nums) {
    int mx = 0;                 // best AND equals the largest element
    for (int v : nums) mx = Math.max(mx, v);
    int best = 0;               // longest valid run so far
    int cur = 0;                // length of current run of mx
    for (int v : nums) {
        if (v == mx) {
            cur++;
            best = Math.max(best, cur);
        } else {
            cur = 0;            // run broken, reset
        }
    }
    return best;
}

int longestSubarray(vector<int>& nums) {
    int mx = *max_element(nums.begin(), nums.end());
    int best = 0;               // longest valid run so far
    int cur = 0;                // length of current run of mx
    for (int v : nums) {
        if (v == mx) {
            cur++;
            best = max(best, cur);
        } else {
            cur = 0;            // run broken, reset
        }
    }
    return best;
}

Explanation

The puzzle looks like it needs us to test every subarray, but a bitwise fact collapses it instantly. The AND of two values can only clear bits, never set them, so for any two different numbers a and b we have a & b < max(a, b). Extending a subarray with any value that isn't already the running AND can only shrink it.

Therefore the largest AND achievable by any subarray is just the largest single element k = max(nums), realized by the one-element subarray containing that maximum. No multi-element subarray can beat it unless every element in it already equals k.

So the question reduces to: what is the longest stretch of consecutive elements all equal to max(nums)? A run of k's has AND k, and the moment a different (necessarily smaller) value appears the AND drops below k, breaking the run.

We scan once, keeping cur as the length of the current run of mx and best as the longest run seen. Every time we hit mx we extend the run; any other value resets cur to 0.

Example: nums = [1, 2, 3, 3, 2, 2]. Here max = 3. The 3's sit consecutively at indices 2 and 3, giving a run of length 2; that is the answer.

Time: O(n) Space: O(1)