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:

1
2
3
4
5

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:

1
2
3
4
5

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

Intuition

The maximum bitwise AND can be found by checking every possible subarray of nums and calculating the bitwise AND for each subarray. Compare each of these results to find the length of the longest subarray with the maximum bitwise AND.

Approach

  • Iterate over all possible starting points (i) of the subarray.
  • For each starting point, iterate over possible ending points (j), and compute the bitwise AND of the elements in the subarray nums[i:j+1].
  • Track the maximum bitwise AND and the length of the corresponding subarray.

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of the array. This arises because of the nested loop: one for the starting index and another for ending index, and calculate and operation on the numbers in subarray.
  • 🧺 Space complexity: O(1)

Method 2 - 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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)