Longest Subarray With Maximum Bitwise AND - Solution & Explanation

Q: Is Longest Subarray With Maximum Bitwise AND easy or hard?

The problem is labeled Medium on LeetCode but behaves closer to an easy problem once the key insight is recognized. The difficulty lies in understanding that the maximum AND value must equal the maximum element in the array.

Q: Longest Subarray With Maximum Bitwise AND Python/Java solution

Most implementations follow the same pattern: compute max(nums), iterate through the array, count consecutive occurrences of that value, and track the maximum length. This logic translates directly to Python, Java, C++, C#, and JavaScript.

Q: How to solve Longest Subarray With Maximum Bitwise AND in O(n)?

First compute the maximum element in the array. Then iterate through the array while counting consecutive elements equal to that maximum value. Reset the counter when a different number appears and keep track of the longest streak.

Q: What is the best approach for Longest Subarray With Maximum Bitwise AND?

The optimal approach finds the maximum element in the array and then counts the longest consecutive sequence of that value. Any subarray AND involving a smaller number will drop below the maximum. This allows a simple O(n) scan with O(1) extra space.

Q: Is Longest Subarray With Maximum Bitwise AND asked at Google/Amazon/Meta?

Bit manipulation and array reasoning problems similar to this frequently appear in interviews at companies like Google, Amazon, and Meta. The key skill tested is recognizing properties of bitwise AND and reducing the problem to a linear scan.

Q: What data structure is used in Longest Subarray With Maximum Bitwise AND?

The solution primarily uses arrays and simple counters. No advanced data structures are required because the key observation reduces the problem to scanning the array and tracking consecutive maximum values.

Q: What is the time complexity of Longest Subarray With Maximum Bitwise AND?

The optimal solution runs in O(n) time and O(1) space. You scan the array once to find the maximum value and once more (or in the same pass) to count the longest streak of that value.

MediumArray Bit Manipulation Brainteaser18 min readAsked at: Amazon, Microsoft, Meta +3

Practice this problem

Problem Statement

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
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
Explanation:
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 <= 10⁵
1 <= nums[i] <= 10⁶

Approach Overview

Problem Overview: Given an integer array nums, return the length of the longest contiguous subarray whose bitwise AND value is as large as possible. The trick is realizing what the maximum possible AND value of any subarray can actually be.

The bitwise AND of multiple numbers can never exceed the largest number in the array. In practice, adding more elements to an AND operation usually decreases the value because bits drop to 0 whenever any number has that bit unset. That observation drives the optimal solution.

Approach 1: Finding Maximum Element (O(n) time, O(1) space)

The maximum bitwise AND obtainable from any subarray is simply the maximum value in nums. Any AND involving a smaller number clears at least one bit, producing a result smaller than that maximum. Because of this, the only way to achieve the maximum AND value is to take subarrays where every element equals the maximum number.

The algorithm is straightforward: first compute max_val = max(nums). Then iterate through the array and count consecutive elements equal to max_val. Track the longest streak. Each streak represents a subarray whose AND equals max_val. This single pass produces the answer in linear time.

This solution relies on properties of bit manipulation. Since AND operations only remove bits, the maximum achievable result must already exist as an element in the array. The rest of the problem reduces to a simple scan over an array.

Approach 2: Sliding Window for Maximum AND Subarray (O(n) time, O(1) space)

You can also think about the problem using a sliding window. First determine the global maximum value in the array. Then expand a window while elements remain equal to that maximum. The moment a smaller value appears, the window must reset because including that element would drop the AND result below the maximum.

The window effectively tracks runs of the maximum element. Maintain two pointers or simply a running length of the current window. When nums[i] == max_val, extend the window. Otherwise reset it to zero. Record the largest window size encountered during the scan.

This framing is useful if you are practicing sliding window patterns. Conceptually, the window represents the longest valid segment where the AND result remains equal to the maximum possible value.

Recommended for interviews: Interviewers usually expect the maximum-element insight. A brute force approach that computes AND for every subarray quickly becomes O(n^2) or worse. Recognizing the bitwise property that the AND cannot exceed the maximum element leads directly to the optimal O(n) scan. Demonstrating that reasoning shows strong understanding of both bit manipulation behavior and efficient array traversal.

Approach 1: Finding Maximum Element

This approach involves finding the maximum element in the array since it would potentially be the maximum bitwise AND when considered individually or consecutively. Then, we scan through the array to find the longest subarray containing only this element.

The code finds the maximum element in the array and then iterates through the array to find the longest contiguous subarray of this maximum element. If a new maximum element is found, it resets the count.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) because we iterate through the array once.

Space Complexity: O(1) as no extra space is used apart from variables.

Try this approach in the editor →

Approach 2: Sliding Window for Maximum AND Subarray

This approach involves using a sliding window to determine the longest subarray where the bitwise AND remains at its maximum value. Begin from the end of the array since the maximum AND value after considering all elements is often the last element itself or a combination found traversing backward.

Initially, the maximum AND is assumed to be the last element. A reverse scan utilizing a sliding window calculates the longest subarray conforming to this value.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), as it involves a single backward traversal.

Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Brain Teaser

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

The problem can be converted to finding the maximum number of consecutive occurrences of the maximum value in the array.

First, traverse the array nums to find the maximum value mx, then traverse the array again to find the maximum number of consecutive occurrences of the maximum value. Finally, return this count.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

Python Java C++Go TypeScript Rust JavaScript C#PHP

Python

Java

C++

TypeScript

Rust

JavaScript

PHP

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Finding Maximum Element	Time Complexity: O(n) because we iterate through the array once. Space Complexity: O(1) as no extra space is used apart from variables.
Sliding Window for Maximum AND Subarray	Time Complexity: O(n), as it involves a single backward traversal. Space Complexity: O(1).
Brain Teaser	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Finding Maximum Element	O(n)	O(1)	Best general solution. Uses the key insight that the maximum AND equals the array's maximum element.
Sliding Window for Maximum AND Subarray	O(n)	O(1)	Useful when practicing sliding window patterns. Conceptually tracks longest segment of the maximum value.

Video Solution

Longest Subarray With Maximum Bitwise AND - Leetcode 2419 - Python • NeetCodeIO • 7,430 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Subarray With Maximum Bitwise AND easy or hard?

The problem is labeled Medium on LeetCode but behaves closer to an easy problem once the key insight is recognized. The difficulty lies in understanding that the maximum AND value must equal the maximum element in the array.

Longest Subarray With Maximum Bitwise AND Python/Java solution

Most implementations follow the same pattern: compute max(nums), iterate through the array, count consecutive occurrences of that value, and track the maximum length. This logic translates directly to Python, Java, C++, C#, and JavaScript.

How to solve Longest Subarray With Maximum Bitwise AND in O(n)?

First compute the maximum element in the array. Then iterate through the array while counting consecutive elements equal to that maximum value. Reset the counter when a different number appears and keep track of the longest streak.

What is the best approach for Longest Subarray With Maximum Bitwise AND?

The optimal approach finds the maximum element in the array and then counts the longest consecutive sequence of that value. Any subarray AND involving a smaller number will drop below the maximum. This allows a simple O(n) scan with O(1) extra space.

Is Longest Subarray With Maximum Bitwise AND asked at Google/Amazon/Meta?

Bit manipulation and array reasoning problems similar to this frequently appear in interviews at companies like Google, Amazon, and Meta. The key skill tested is recognizing properties of bitwise AND and reducing the problem to a linear scan.

What data structure is used in Longest Subarray With Maximum Bitwise AND?

The solution primarily uses arrays and simple counters. No advanced data structures are required because the key observation reduces the problem to scanning the array and tracking consecutive maximum values.

What is the time complexity of Longest Subarray With Maximum Bitwise AND?

The optimal solution runs in O(n) time and O(1) space. You scan the array once to find the maximum value and once more (or in the same pass) to count the longest streak of that value.

Ready to solve this problem?

Practice Longest Subarray With Maximum Bitwise AND with our built-in code editor and test cases.

Practice on FleetCode

Count Number of Maximum Bitwise-OR Subsets

Number of Different Integers in a String

Problem Info

DifficultyMedium

Acceptance65.4%

Approaches3

Reading time18 min

Asked at

Amazon Microsoft Meta Google Bloomberg

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Finding Maximum Element

Code

Complexity

Approach 2: Sliding Window for Maximum AND Subarray

Code

Complexity

Approach 3: Brain Teaser

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents