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 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.

Examples

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.

Solution

Method 1 - Two Pass

Key Observations

  1. The bitwise AND operation is particularly different from other operations like sum or XOR in that adding more elements usually decreases the value (a & b <= a for any a, b).
  2. So, the maximum bitwise AND of any subarray is likely to be one of the elements themselves, as adding more elements will generally introduce more 0s into the bitwise AND, reducing its value.
  3. We need to identify the maximum bitwise AND value k first, which will be the maximum number in the array. Then, find the longest contiguous subarray where all elements are equal to this maximum value.

Solution Approach

  1. Find the maximum element k in the array.
  2. Iterate through the array to find the longest sequence of contiguous elements equal to k.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
public class Solution {
    public int longestSubarray(int[] nums) {
        // Step 1: Find the maximum number in the array
        int maxVal = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num > maxVal) {
                maxVal = num;
            }
        }

        // Step 2: Find the longest contiguous subarray where all elements are
        // equal to max_value
        int maxLen = 0;
        int currLen = 0;

        for (int num : nums) {
            if (num == maxVal) {
                currLen++;
                maxLen = Math.max(maxLen, currLen);
            } else {
                currLen = 0;
            }
        }

        return maxLen;
    }
}
Python
class Solution(object):
    def longestSubarray(self, nums):
        # Step 1: Find the maximum number in the array
        max_value = max(nums)

        # Step 2: Find the longest contiguous subarray where all elements are equal to max_value
        max_length = 0
        current_length = 0

        for num in nums:
            if num == max_value:
                current_length += 1
                max_length = max(max_length, current_length)
            else:
                current_length = 0

        return max_length

Complexity

  • ⏰ Time complexity: O(n)
    • The loop to find the maximum element in the array nums takes O(n) time, where n is the length of nums.
    • The loop to find the longest contiguous subarray where all elements are equal to max_value also takes (O(n)) time.
  • 🧺 Space complexity: O(1)