#2419

Medium

LeetCode Problem Workspace

Longest Subarray With Maximum Bitwise AND

Find the length of the longest subarray whose bitwise AND reaches the array's maximum value, combining array scanning with bit manipulation logic.

array bit manipulation brainteaser

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.

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.

terminal

Solution

Solution 1: Brain Teaser

Since the bitwise AND operation does not increase the number, the maximum value is the maximum value in the array.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        mx = max(nums)
        ans = cnt = 0
        for x in nums:
            if x == mx:
                cnt += 1
                ans = max(ans, cnt)
            else:
                cnt = 0
        return ans

Continue Practicing

#2425 bitwise xor of all pairings #2568 minimum impossible or #2411 smallest subarrays with maximum bitwise or