LeetCode 2419 - Longest Subarray With Maximum Bitwise AND

The problem asks us to find the length of the longest subarray within a given array nums such that the bitwise AND of all elements in that subarray is maximized.

leetcodemediumarraybit-manipulationbrainteaser

LeetCode Problem 2419

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Brainteaser

Solution

Problem Understanding

The problem asks us to find the length of the longest subarray within a given array nums such that the bitwise AND of all elements in that subarray is maximized. In simpler terms, we first need to identify the largest possible bitwise AND we can get from any subarray, and then determine the contiguous subarray(s) that achieve this AND and have the greatest length.

The input nums is a list of integers, each in the range 1 to 10^6, and the length of nums can be up to 10^5. The output is a single integer, which represents the length of the longest contiguous subarray with the maximum bitwise AND.

Constraints tell us that a naive approach, like checking all possible subarrays, would be too slow because the number of subarrays grows quadratically with n. Also, since all numbers are positive integers, the maximum AND will always be one of the numbers in nums.

Edge cases to consider include:

  • All numbers being equal, which would make the entire array a valid subarray.
  • A strictly decreasing or increasing array where only single elements achieve the maximum AND.
  • Arrays with multiple occurrences of the maximum number.

Approaches

The brute-force approach would be to generate every possible subarray, compute the bitwise AND for each, track the maximum AND, and then determine the longest subarray that achieves it. While this is correct logically, it is computationally infeasible because computing all subarrays requires O(n^2) time, and computing AND for each subarray could take up to O(n) per subarray, resulting in O(n^3) overall.

The optimal approach relies on the key observation that the maximum bitwise AND is equal to the maximum element in the array. This is because ANDing numbers can only reduce or maintain the bits, never increase them. Therefore, only the contiguous segments consisting entirely of the maximum number can achieve this maximum AND. This reduces the problem to finding the length of the longest contiguous subarray of the maximum element.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Check all subarrays and compute AND
Optimal O(n) O(1) Find max element, then find longest contiguous segment of that value

Algorithm Walkthrough

  1. Traverse the array to find the maximum element, max_val. This represents the largest possible bitwise AND.

  2. Initialize two variables: current_length to track the length of a contiguous segment of max_val, and max_length to track the maximum segment length found.

  3. Iterate through the array. For each element:

  4. If the element equals max_val, increment current_length.

  5. If the element does not equal max_val, reset current_length to 0.

  6. After each increment, update max_length if current_length is larger than max_length.

  7. After completing the iteration, max_length contains the length of the longest contiguous subarray with maximum AND.

Why it works: The bitwise AND of any subarray that includes a number smaller than the maximum element will always be less than max_val. Therefore, only segments containing exclusively the maximum element achieve the maximum AND, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        max_val = max(nums)
        max_length = 0
        current_length = 0
        
        for num in nums:
            if num == max_val:
                current_length += 1
                max_length = max(max_length, current_length)
            else:
                current_length = 0
        
        return max_length

This implementation first identifies the maximum element and then counts the length of contiguous sequences of this value. current_length resets whenever a smaller element interrupts the sequence, ensuring we only consider valid subarrays.

Go Solution

func longestSubarray(nums []int) int {
    maxVal := 0
    for _, num := range nums {
        if num > maxVal {
            maxVal = num
        }
    }

    maxLength := 0
    currentLength := 0
    for _, num := range nums {
        if num == maxVal {
            currentLength++
            if currentLength > maxLength {
                maxLength = currentLength
            }
        } else {
            currentLength = 0
        }
    }
    return maxLength
}

In Go, the logic is identical. We use a simple for loop to find the maximum and then a second loop to determine the length of contiguous segments equal to maxVal. Slices in Go handle iteration efficiently, and no extra memory is required.

Worked Examples

Example 1: nums = [1,2,3,3,2,2]

max_val = 3

Iteration over nums:

Element current_length max_length
1 0 0
2 0 0
3 1 1
3 2 2
2 0 2
2 0 2

Return 2.

Example 2: nums = [1,2,3,4]

max_val = 4

Iteration over nums:

Element current_length max_length
1 0 0
2 0 0
3 0 0
4 1 1

Return 1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Two passes over the array: one for max, one for longest segment
Space O(1) Only integer variables are used, no extra memory needed

The optimal algorithm only requires simple integer variables to track the maximum and current lengths, making it highly space efficient.

Test Cases

# Provided examples
assert Solution().longestSubarray([1,2,3,3,2,2]) == 2  # contiguous max elements
assert Solution().longestSubarray([1,2,3,4]) == 1      # single max element

# Edge cases
assert Solution().longestSubarray([5,5,5,5]) == 4       # all elements same
assert Solution().longestSubarray([1,1,2,1,1]) == 1    # max element isolated
assert Solution().longestSubarray([2]) == 1            # single element
assert Solution().longestSubarray([1,2,2,2,1,2,2]) == 3 # multiple segments
assert Solution().longestSubarray([1,1,1,1,1,0,1]) == 5 # segment at start
Test Why
[1,2,3,3,2,2] Validates multiple max elements in a segment
[1,2,3,4] Only one element is max
[5,5,5,5] Entire array is max
[1,1,2,1,1] Max element isolated, check reset
[2] Single element array
[1,2,2,2,1,2,2] Multiple segments, check longest is chosen
[1,1,1,1,1,0,1] Max segment at start

Edge Cases

  1. All elements are the same: In this case, the maximum AND equals the element itself, and the entire array is the longest subarray. The algorithm handles this naturally because it counts all contiguous max elements.
  2. Single-element array: The maximum AND is the element itself, and the longest subarray is of length 1. The algorithm works since current_length increments once and max_length is updated.
  3. Multiple segments of max elements: If there are multiple non-contiguous segments with the maximum value, the algorithm correctly identifies the longest one by updating max_length whenever current_length exceeds it.

This approach efficiently handles the constraints and edge cases without extra memory or complex data structures.