Longest Subarray With Maximum Bitwise AND solution and explanation
Google
9 more videos on this problem
Longest Subarray With Maximum Bitwise AND - Leetcode 2419 - PythonNeetCodeIO · 14:41 · 7K views
Leetcode 2419 Longest Subarray With Maximum Bitwise AND |Coding Decoded SDE SheetCoding Decoded · 5:34 · 2K views
2419. Longest Subarray With Maximum Bitwise AND (Leetcode Medium)Programming Live with Larry · 5:07 · 391 views
2419. Longest Subarray With Maximum Bitwise AND | Leetcode Daily - PythonLeetcode Daily · 4:13 · 214 views
Longest Subarray With Maximum Bitwise AND | LeetCode 2419 - Pythonimpoldev · 6:52 · 148 views
LeetCode 2419 - Longest Subarray With Maximum Bitwise And - JavaAlpha-Code · 8:25 · 83 views
Longest Subarray With Maximum Bitwise AND - Leetcode 2419 - JavaCode With K5KC · 5:49 · 68 views
2419. Longest Subarray With Maximum Bitwise AND Leetcode Solution | Bit Manipulation | MathKevin Tamakuwala · 18:05 · 63 views
2419 Longest Subarray With Maximum Bitwise ANDR Sai Siddhu · 8:30 · 48 views
Leetcode Daily 2419. Longest Subarray With Maximum Bitwise ANDDilan Rocco · 6:06 · 40 views
The problem
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
kbe the maximum value of the bitwise AND of any subarray ofnums. Then, only subarrays with a bitwise AND equal tokshould 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 <= 1051 <= nums[i] <= 106
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.
def longest_max_and_subarray(nums):
max_element = 0
current_length = 0
longest_length = 0
for num in nums:
if num > max_element:
max_element = num
current_length = 1
longest_length = 1
elif num == max_element:
current_length += 1
longest_length = max(longest_length, current_length)
else:
current_length = 0
return longest_length
nums = [1, 2, 3, 3, 2, 2]
print(longest_max_and_subarray(nums))public class Solution {
public int longestMaxAndSubarray(int[] nums) {
int maxElement = 0, currentLength = 0, longestLength = 0;
for (int num : nums) {
if (num > maxElement) {
maxElement = num;
currentLength = 1;
longestLength = 1;
} else if (num == maxElement) {
currentLength++;
longestLength = Math.max(longestLength, currentLength);
} else {
currentLength = 0;
}
}
return longestLength;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 3, 2, 2};
System.out.println(sol.longestMaxAndSubarray(nums));
}
}#include <vector>
#include <iostream>
int longestMaxAndSubarray(std::vector<int>& nums) {
int maxElement = 0, currentLength = 0, longestLength = 0;
for (int num : nums) {
if (num > maxElement) {
maxElement = num;
currentLength = 1;
longestLength = 1;
} else if (num == maxElement) {
currentLength++;
longestLength = std::max(longestLength, currentLength);
} else {
currentLength = 0;
}
}
return longestLength;
}
int main() {
std::vector<int> nums = {1, 2, 3, 3, 2, 2};
std::cout << longestMaxAndSubarray(nums) << std::endl;
return 0;
}function longestMaxAndSubarray(nums) {
let maxElement = 0;
let currentLength = 0;
let longestLength = 0;
for (let num of nums) {
if (num > maxElement) {
maxElement = num;
currentLength = 1;
longestLength = 1;
} else if (num === maxElement) {
currentLength++;
longestLength = Math.max(longestLength, currentLength);
} else {
currentLength = 0;
}
}
return longestLength;
}
const nums = [1, 2, 3, 3, 2, 2];
console.log(longestMaxAndSubarray(nums));#include <stdio.h>
int longestMaxAndSubarray(int* nums, int numsSize) {
int maxElement = 0, currentLength = 0, longestLength = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > maxElement) {
maxElement = nums[i];
currentLength = 1;
longestLength = 1;
} else if (nums[i] == maxElement) {
currentLength++;
if (currentLength > longestLength) {
longestLength = currentLength;
}
} else {
currentLength = 0;
}
}
return longestLength;
}
int main() {
int nums[] = {1, 2, 3, 3, 2, 2};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", longestMaxAndSubarray(nums, numsSize));
return 0;
}using System;
public class Solution {
public int LongestMaxAndSubarray(int[] nums) {
int maxElement = 0, currentLength = 0, longestLength = 0;
foreach (int num in nums) {
if (num > maxElement) {
maxElement = num;
currentLength = 1;
longestLength = 1;
} else if (num == maxElement) {
currentLength++;
longestLength = Math.Max(longestLength, currentLength);
} else {
currentLength = 0;
}
}
return longestLength;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 3, 2, 2};
Console.WriteLine(sol.LongestMaxAndSubarray(nums));
}
}This Python function utilizes a similar logic to find the longest subarray having the maximum element.
Time Complexity: O(n).
Space Complexity: O(1).
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.
def longest_subarray(nums):
max_and = nums[-1]
longest = 0
count = 0
for num in reversed(nums):
if (max_and & num) == max_and:
count += 1
longest = max(longest, count)
else:
count = 0
return longest
nums = [1, 2, 3, 3, 2, 2]
print(longest_subarray(nums))public class Solution {
public int longestSubarray(int[] nums) {
int maxAnd = nums[nums.length - 1];
int longest = 0, count = 0;
for (int i = nums.length - 1; i >= 0; i--) {
if ((maxAnd & nums[i]) == maxAnd) {
count++;
longest = Math.max(longest, count);
} else {
count = 0;
}
}
return longest;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 3, 2, 2};
System.out.println(sol.longestSubarray(nums));
}
}#include <vector>
#include <iostream>
int longestSubarray(std::vector<int>& nums) {
int maxAnd = nums.back();
int longest = 0, count = 0;
for (auto it = nums.rbegin(); it != nums.rend(); ++it) {
if ((maxAnd & *it) == maxAnd) {
count++;
longest = std::max(longest, count);
} else {
count = 0;
}
}
return longest;
}
int main() {
std::vector<int> nums = {1, 2, 3, 3, 2, 2};
std::cout << longestSubarray(nums) << std::endl;
return 0;
}function longestSubarray(nums) {
let maxAnd = nums[nums.length - 1];
let longest = 0;
let count = 0;
for (let i = nums.length - 1; i >= 0; i--) {
if ((maxAnd & nums[i]) === maxAnd) {
count++;
longest = Math.max(longest, count);
} else {
count = 0;
}
}
return longest;
}
const nums = [1, 2, 3, 3, 2, 2];
console.log(longestSubarray(nums));#include <stdio.h>
int longestSubarray(int* nums, int numsSize) {
int maxAnd = nums[numsSize - 1];
int longest = 0, count = 0;
for (int i = numsSize - 1; i >= 0; i--) {
if ((maxAnd & nums[i]) == maxAnd) {
count++;
if (count > longest) longest = count;
} else {
count = 0;
}
}
return longest;
}
int main() {
int nums[] = {1, 2, 3, 3, 2, 2};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", longestSubarray(nums, numsSize));
return 0;
}using System;
public class Solution {
public int LongestSubarray(int[] nums) {
int maxAnd = nums[nums.Length - 1];
int longest = 0, count = 0;
for (int i = nums.Length - 1; i >= 0; i--) {
if ((maxAnd & nums[i]) == maxAnd) {
count++;
longest = Math.Max(longest, count);
} else {
count = 0;
}
}
return longest;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 3, 2, 2};
Console.WriteLine(sol.LongestSubarray(nums));
}
}This Python function checks for maintaining the assumed maximum AND using a sliding window, iterating over elements from the back.
Time Complexity: O(n).
Space Complexity: O(1).
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).
function longestSubarray(nums: number[]): number {
const mx = Math.max(...nums);
let [ans, cnt] = [0, 0];
for (const x of nums) {
if (x === mx) {
ans = Math.max(ans, ++cnt);
} else {
cnt = 0;
}
}
return ans;
}func longestSubarray(nums []int) (ans int) {
mx := slices.Max(nums)
cnt := 0
for _, x := range nums {
if x == mx {
cnt++
ans = max(ans, cnt)
} else {
cnt = 0
}
}
return
}impl Solution {
pub fn longest_subarray(nums: Vec<i32>) -> i32 {
let mx = *nums.iter().max().unwrap();
let mut ans = 0;
let mut cnt = 0;
for &x in nums.iter() {
if x == mx {
cnt += 1;
ans = ans.max(cnt);
} else {
cnt = 0;
}
}
ans
}
}class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function longestSubarray($nums) {
$mx = max($nums);
$ans = 0;
$cnt = 0;
foreach ($nums as $x) {
if ($x == $mx) {
$ans = max($ans, ++$cnt);
} else {
$cnt = 0;
}
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Finding Maximum Element | Time Complexity: O(n). Space Complexity: O(1). |
| Sliding Window for Maximum AND Subarray | Time Complexity: O(n). Space Complexity: O(1). |
| Brain Teaser | – |
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. |
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.