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
- The AND of a subarray is at most the smallest element in it, which is at most the global maximum
max(nums). - The value
max(nums)is achievable, by the single-element subarray holding that maximum. - To have an AND equal to
max(nums), every element of the subarray must equalmax(nums); any smaller element would clear bits and drop the AND below it. - 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.