We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Subarray With Maximum Bitwise AND

Number: 2503

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Siemens, fourkites

Problem Description

Given an integer array nums, find the longest contiguous subarray whose bitwise AND equals the maximum value obtainable by any subarray. The maximum bitwise AND is achieved by a subarray containing only occurrences of the maximum element in nums. Return the length of the longest such subarray.

Key Insights

  • The bitwise AND of any subarray can never exceed the minimum element in that subarray.
  • For the bitwise AND to be maximum overall, the subarray must consist solely of the maximum element in nums.
  • The problem reduces to finding the longest contiguous sequence of the maximum element in the array.

Space and Time Complexity

Time Complexity: O(n) – We traverse the array once. Space Complexity: O(1) – Only constant extra space is used.

Solution

  1. Find the maximum element in the given array nums.
  2. Iterate through nums to compute the length of each contiguous subarray that contains only this maximum element.
  3. Track and return the length of the longest such subarray.

Data Structures/Algorithms used:

  • Single pass iteration for both finding max value and counting contiguous subarrays.
  • Constant extra space using variables to track maximum value and current streak length.

Code Solutions

# Function to return the length of the longest subarray with maximum bitwise AND
def longest_subarray_with_max_bitwise_and(nums):
    # Find the maximum value in nums
    max_value = max(nums)
    
    max_length = 0  # Will store the longest contiguous sequence length
    current_length = 0  # Current streak of maximum elements
    
    # Iterate through the array
    for num in nums:
        if num == max_value:
            # Increment current streak if the element equals the maximum value
            current_length += 1
            max_length = max(max_length, current_length)
        else:
            # Reset streak if element is not the maximum
            current_length = 0
            
    return max_length

# Example usage:
print(longest_subarray_with_max_bitwise_and([1,2,3,3,2,2]))  # Output: 2
print(longest_subarray_with_max_bitwise_and([1,2,3,4]))        # Output: 1
← Back to All Questions