Start by identifying the maximum value in the array since the longest subarray must contain only this value for maximum bitwise AND. Then, iterate through the array while counting consecutive elements equal to the maximum. This approach ensures O(N) time and O(1) space while directly addressing the Array plus Bit Manipulation pattern in this problem.
Problem Statement
You are given an integer array nums. Your task is to find a non-empty subarray where the bitwise AND of all its elements equals the largest possible AND achievable in the array. Return the length of the longest such subarray.
For example, given nums = [1,2,3,3,2,2], the maximum bitwise AND is 3. The longest contiguous subarray that achieves this AND is [3,3], with length 2. Constraints ensure 1 <= nums.length <= 10^5 and 1 <= nums[i] <= 10^6.
Examples
Example 1
Input: nums = [1,2,3,3,2,2]
Output: 2
The maximum possible bitwise AND of a subarray is 3. The longest subarray with that value is [3,3], so we return 2.
Example 2
Input: nums = [1,2,3,4]
Output: 1
The maximum possible bitwise AND of a subarray is 4. The longest subarray with that value is [4], so we return 1.
Constraints
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 106
Solution Approach
Identify the maximum value
Scan the array once to find the maximum number. Since any bitwise AND of numbers less than the maximum cannot equal the maximum, only sequences of the maximum matter.
Track consecutive maximums
Iterate through nums while counting consecutive elements equal to the maximum. Reset the count when a smaller element appears, keeping track of the largest count found.
Return the longest length
After scanning the entire array, the maximum count represents the length of the longest subarray achieving the maximum bitwise AND. This completes the O(N) solution with O(1) space.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N) |
| Space | O(1) |
Time complexity is O(N) for a single pass to find maximum and scan subarrays. Space complexity is O(1) since only counters are maintained, no extra structures.
What Interviewers Usually Probe
- Expect recognition that bitwise AND is maximized by the largest single number.
- Look for O(N) single-pass solutions avoiding nested loops.
- Check if candidate counts consecutive maximum elements correctly.
Common Pitfalls or Variants
Common pitfalls
- Confusing bitwise AND logic and trying to AND all subarrays explicitly.
- Using extra arrays or sets, which increases space unnecessarily.
- Failing to reset the consecutive count when a smaller element appears.
Follow-up variants
- Find longest subarray with minimum bitwise OR instead of AND.
- Determine the longest subarray where all elements are equal to a given target.
- Count the number of subarrays achieving the maximum bitwise AND instead of the longest length.
How GhostInterview Helps
- Highlights the maximum-value filtering strategy to simplify bitwise AND calculations.
- Guides on scanning and counting consecutive maximums without extra space.
- Explains trade-offs of naive subarray checks versus direct linear iteration.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
Why do we only consider the maximum value in the array?
Because any bitwise AND with a smaller number cannot equal the maximum, so only subarrays containing the maximum can achieve it.
Can we use a sliding window for this problem?
Yes, effectively the consecutive maximum counting acts like a sliding window over segments of maximum numbers.
Does this approach work for very large arrays?
Yes, it is O(N) in time and O(1) in space, handling arrays up to 10^5 elements efficiently.
What pattern does this problem illustrate?
It exemplifies the Array plus Bit Manipulation pattern, focusing on filtering elements by maximum value for AND operations.
Can bitwise ANDs of different numbers equal the maximum?
No, combining two different numbers always produces a value less than the larger number, so only consecutive maximums work.
Need direct help with Longest Subarray With Maximum Bitwise AND instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Longest Subarray With Maximum Bitwise AND from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Compute the overall bitwise XOR from all pairings between two arrays using efficient array and bit manipulation techniques.
Open problem page#2568 Minimum Impossible ORFind the smallest positive integer that cannot be formed from any subsequence OR combination in the array.
Open problem page#2411 Smallest Subarrays With Maximum Bitwise ORFind the smallest subarrays with the maximum bitwise OR for each starting index in an array.
Open problem page