⚡Flashcard Drill➔
NeetCode #876LC-2419MediumBit Manipulation
← Back to All Problems

#876 · #2419 · Longest Subarray With Maximum Bitwise AND(按位与最大的最长子数组)

📌 Problem Statement & Constraints

Given an array nums of integers, return the length of the longest subarray whose bitwise AND equals the maximum AND achievable by any subarray. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^6.

💡 Core Algorithmic Approaches

  1. The AND of a subarray is at most the smallest element in it, which is at most the global maximum max(nums).
  2. The value max(nums) is achievable, by the single-element subarray holding that maximum.
  3. To have an AND equal to max(nums), every element of the subarray must equal max(nums); any smaller element would clear bits and drop the AND below it.
  4. So the answer is the length of the longest contiguous run of elements equal to max(nums).

💻 Benchmark Python3 Implementation

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        mx = max(nums)
        best = 0
        cur = 0
        for x in nums:
            if x == mx:
                cur += 1
                best = max(best, cur)
            else:
                cur = 0                 # the run of maximums is broken
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): three scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Computing the AND of every subarray: O(n^2) and unnecessary; the answer is a run-length count.
  • Allowing smaller elements in the subarray: the AND would drop below the maximum, so only elements equal to the maximum qualify.
  • Confusing this with the maximum subarray sum: the objective is the AND, not the sum.
  • Forgetting that a single element counts: a subarray of length 1 is valid, so the answer is at least 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems