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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Subarray With Maximum Bitwise AND

Difficulty: Medium

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. Return the length of the longest such subarray.

Key Insights

  • The maximum bitwise AND of a subarray is determined by the largest element in the array, as the bitwise AND operation can only retain bits that are set in all numbers.
  • To find the longest subarray with the maximum bitwise AND, we need to identify the maximum value in the array and then count the length of the contiguous segments where this maximum value appears.
  • The problem can be efficiently solved in a single pass through the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves finding the maximum value in the array and then scanning through the array to find the longest contiguous segment of that maximum value. We keep track of the current length of the segment and update the maximum length whenever we encounter a break in the segment.

Code Solutions

def longestSubarray(nums):
    max_value = max(nums)  # Find the maximum value in the array
    max_length = 0
    current_length = 0
    
    for num in nums:
        if num == max_value:
            current_length += 1  # Increment length of current segment
            max_length = max(max_length, current_length)  # Update max length found
        else:
            current_length = 0  # Reset length when encountering a different number
            
    return max_length
← Back to All Questions