Leetcode Daily Question 14/09/2024 - 2419. Longest Subarray With Maximum Bitwise AND

Problem Description:

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.

from typing import List
class Solution:
  def longestSubarray(self, nums: List[int]) -> int:
    max_elt = float('-inf')
    max_length = 0
    curr_length = 0
    for num in nums:
      if num > max_elt:
        max_elt = num
        curr_length = 1
        max_length = 1
      elif num == max_elt:
        curr_length += 1
        max_length = max(max_length, curr_length)
      else:
        curr_length = 0
    
    return max_length

Explanation:

To solve this, we need to understand what the bitwise AND operator does to two elements.

Consider the two positive integers, 4, 5. 
In binary they are "100" and "101" respectively. 
The AND operator only set the bit if both bits match in the two numbers.
So since only the least significat bit matches, the answer is "100" in binary or 4 in decimal.

More generally, if we have two positive integers a, b, where a <= b.
Suppose they have the same amount of bits in their binary reps.
Then b must have more set bits towards the left end. 
This means after applying the AND operator, the maximum the result can be is b.
This occurs if and only if a == b.

So, to solve this. We simply need to count the longest contiguous subarray containing only the maximum element in the array.

We start initiating the variables, max_elt, denoting max element of the array, curr_length, the current length of the contiguous array found, and max_length, the maximum length of the array which also acts as the output of the function.

We traverse the array number by number. We first check if the current number if larger than our max. If it is, we put max as this new number and update max_length and current_length as 1 (the minimum length of any subarray is 1)

Else if the number we encounter is the same as max, then we increment curr_length and take max with max_length.

Else, we have encountered an element that is not equal to max and is not larger than max. We reset our curr_length count to 0 to start over.

def longestSubarray(nums):
  max_elt = float('-inf')
  curr_length = 0
  max_length = 0
  for num in nums:
    if num > max_elt:
      max_elt = num
      curr_length = 1
      max_length = 1
    elif num == max_elt:
      curr_length += 1
      max_length = max(max_length, curr_length)
    else:
      curr_length = 0
  return max_length

The time complexity is O(n) as we need to traverse the entire array exactly once.

The space complexity is O(n) as all variables stored are constant variables.

The full solution can be found near the top of the page.