Longest Subarray With Maximum Bitwise AND

Med

#2203Time: O(n^2), where n is the length of the input array `nums`. The nested loops result in a quadratic number of operations as we check every possible subarray.Space: O(1) extra space, as we only use a few variables to store the maximum AND value, max length, and current AND value.1 company

Patterns

Bit Manipulation

Data structures

Array

Companies

fourkites

Prompt

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⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code without leveraging any special properties of the bitwise AND operation. It systematically considers every possible contiguous subarray, calculates its bitwise AND, and keeps track of the maximum AND value seen so far (maxAndVal) and the length of the longest subarray that results in that value (maxLength).

Algorithm

Initialize maxAndVal = 0 and maxLength = 0.
Iterate through the array with an outer loop index i from 0 to n-1 to select a starting element for the subarray.
Inside the outer loop, initialize currentAnd with the value of nums[i].
Start an inner loop with index j from i to n-1 to extend the subarray to the right.
In each step of the inner loop, currentAnd represents the bitwise AND of the subarray nums[i...j].
Compare currentAnd with maxAndVal:
- If currentAnd > maxAndVal, we have found a new maximum AND value. Update maxAndVal to currentAnd and set maxLength to the current subarray's length (j - i + 1).
- If currentAnd == maxAndVal, we have found another subarray with the same maximum AND. Update maxLength to be the maximum of its current value and the new subarray's length.
After both loops complete, maxLength will hold the length of the longest subarray that has the maximum possible bitwise AND value.

Walkthrough

We use two nested loops to generate all possible subarrays. The outer loop, indexed by i, determines the start of the subarray. The inner loop, indexed by j, determines the end. For each starting position i, we initialize a variable currentAnd. As we extend the subarray by moving j to the right, we update currentAnd by performing a bitwise AND with the new element nums[j]. This is more efficient than recalculating the AND from scratch for every subarray. At each step, we compare the currentAnd of the subarray nums[i...j] with our global maxAndVal. If we find a strictly greater AND value, we update maxAndVal and reset maxLength. If we find an equal AND value, we only update maxLength if the current subarray is longer.

1class Solution {2    public int longestSubarray(int[] nums) {3        int maxAndVal = 0;4        int maxLength = 0;5        int n = nums.length;6 7        for (int i = 0; i < n; i++) {8            int currentAnd = nums[i];9            // Check subarray nums[i...i]10            if (currentAnd > maxAndVal) {11                maxAndVal = currentAnd;12                maxLength = 1;13            } else if (currentAnd == maxAndVal) {14                maxLength = Math.max(maxLength, 1);15            }16            17            for (int j = i + 1; j < n; j++) {18                currentAnd &= nums[j];19                // Check subarray nums[i...j]20                if (currentAnd > maxAndVal) {21                    maxAndVal = currentAnd;22                    maxLength = j - i + 1;23                } else if (currentAnd == maxAndVal) {24                    maxLength = Math.max(maxLength, j - i + 1);25                }26            }27        }28        return maxLength;29    }30}

Complexity

Time

O(n^2), where n is the length of the input array `nums`. The nested loops result in a quadratic number of operations as we check every possible subarray.

Space

O(1) extra space, as we only use a few variables to store the maximum AND value, max length, and current AND value.

Trade-offs

Pros

It is a straightforward implementation that correctly solves the problem.
It does not require any special insights and follows directly from the problem definition.

Cons

The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will likely result in a 'Time Limit Exceeded' error on most platforms.

This optimal approach is based on a crucial property of the bitwise AND operation: for any two numbers a and b, a & b <= min(a, b). This property extends to any number of elements. Consequently, the bitwise AND of any subarray is always less than or equal to the smallest element in that subarray. This implies that the maximum possible bitwise AND of any subarray cannot exceed the maximum element in the entire array.

The maximum value is achievable by a subarray of length 1 containing just the maximum element. Therefore, the problem simplifies to finding the maximum element in the array and then finding the length of the longest contiguous subarray where all elements are equal to this maximum value.

Algorithm

Initialize maxVal = 0 (to store the maximum element found), maxLength = 0 (the final answer), and currentLength = 0 (to track the length of the current run of maxVal).
Iterate through each number num in the input array nums.
For each num:
- If num > maxVal: We've found a new maximum element. This new element forms a new subarray with the highest possible AND value so far. Update maxVal = num, and reset both maxLength and currentLength to 1.
- If num == maxVal: The current run of the maximum element continues. Increment currentLength and update maxLength = max(maxLength, currentLength).
- If num < maxVal: The current run of the maximum element is broken. Reset currentLength = 0.
After iterating through the entire array, return maxLength.

Walkthrough

We can find the solution in a single pass through the array. We maintain three variables: maxVal (the maximum element encountered so far), maxLength (the length of the longest run of maxVal found so far), and currentLength (the length of the current contiguous run of maxVal).

As we iterate through the array, if we encounter a number larger than maxVal, we have a new maximum. We update maxVal and reset our length counters (maxLength and currentLength) to 1. If we encounter a number equal to maxVal, we are extending the current run, so we increment currentLength and update maxLength if this new run is the longest yet. If we see a number smaller than maxVal, it breaks any potential run of maxVal, so we reset currentLength to 0. This single pass efficiently finds both the maximum element and the longest run of it simultaneously.

1class Solution {2    public int longestSubarray(int[] nums) {3        int maxVal = 0;4        int maxLength = 0;5        int currentLength = 0;6 7        for (int num : nums) {8            if (num > maxVal) {9                // Found a new maximum value10                maxVal = num;11                maxLength = 1;12                currentLength = 1;13            } else if (num == maxVal) {14                // Continuing a run of the maximum value15                currentLength++;16                maxLength = Math.max(maxLength, currentLength);17            } else { // num < maxVal18                // The run of the maximum value is broken19                currentLength = 0;20            }21        }22        return maxLength;23    }24}

Complexity

Time

O(n), where n is the length of the input array `nums`. We iterate through the array only once.

Space

O(1) extra space. We only use a constant number of variables to track the state.

Trade-offs

Pros

Extremely efficient, with optimal time and space complexity.
Solves the problem in a single pass over the input array.

Cons

The logic relies on a key insight about the bitwise AND operation, which may not be immediately obvious.

Solutions

Solution

1class Solution {2public3  int longestSubarray(int[] nums) {4    int mx = 0;5    for (int v : nums) {6      mx = Math.max(mx, v);7    }8    int ans = 0, cnt = 0;9    for (int v : nums) {10      if (v == mx) {11        ++cnt;12        ans = Math.max(ans, cnt);13      } else {14        cnt = 0;15      }16    }17    return ans;18  }19}

1function longestSubarray ( nums ) { const mx = Math . max (... nums ); let [ ans , cnt ] = [ 0 , 0 ]; for ( const x of nums ) { if ( x === mx ) { cnt ++ ; ans = Math . max ( ans , cnt ); } else { cnt = 0 ; } } return ans ; }

1class Solution {2public:3  int longestSubarray(vector<int> &nums) {4    int mx = *max_element(nums.begin(), nums.end());5    int ans = 0, cnt = 0;6    for (int v : nums) {7      if (v == mx) {8        ++cnt;9        ans = max(ans, cnt);10      } else {11        cnt = 0;12      }13    }14    return ans;15  }16};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem