2419: Longest Subarray With Maximum Bitwise AND

Problem Statement

Given an integer array nums, find the length of the longest contiguous subarray where the bitwise AND of the subarray equals the maximum possible bitwise AND of any subarray.

The bitwise AND of a subarray is the bitwise AND of all integers in that contiguous segment.

Key Insight

The solution relies on two crucial observations:

1. The maximum possible bitwise AND of any subarray is equal to the maximum element in the array (max_val)
2. The longest subarray with bitwise AND equal to max_val is the longest contiguous segment of max_val in the original array

The longest contiguous segment of max value (3) has length 2. We cannot connect non-adjacent 3's without breaking contiguity.

Optimal Approach: Find Longest Contiguous Segment

This approach finds the longest contiguous segment of the maximum value in the original array.

Algorithm Steps

1. Find the maximum value in the array
2. Traverse the array to find the longest contiguous segment of this maximum value
3. Return the length of this segment

Why This Works

The maximum bitwise AND value can only be achieved by subarrays consisting entirely of the maximum element. The longest such subarray is the longest contiguous segment of this value in the original array.

Complexity Analysis

Where n is the length of the array. We traverse the array once to find the maximum and once to find the longest segment.

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        // Find the maximum value
        int max_val = *max_element(nums.begin(), nums.end());
        int max_len = 0;
        int curr_len = 0;
        
        for (int num : nums) {
            if (num == max_val) {
                curr_len++;
                max_len = max(max_len, curr_len);
            } else {
                curr_len = 0;
            }
        }
        
        return max_len;
    }
};

class Solution {
    public int longestSubarray(int[] nums) {
        // Find the maximum value
        int max_val = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num > max_val) max_val = num;
        }
        
        int max_len = 0;
        int curr_len = 0;
        for (int num : nums) {
            if (num == max_val) {
                curr_len++;
                max_len = Math.max(max_len, curr_len);
            } else {
                curr_len = 0;
            }
        }
        
        return max_len;
    }
}

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        # Find the maximum value
        max_val = max(nums)
        max_len = curr_len = 0
        
        for num in nums:
            if num == max_val:
                curr_len += 1
                max_len = max(max_len, curr_len)
            else:
                curr_len = 0
                
        return max_len

Alternative Approach: Single Pass with Max Tracking

This approach combines finding the maximum value and tracking contiguous segments in a single pass.

Algorithm Steps

1. Initialize variables for current maximum value, current segment length, and maximum segment length
2. Traverse the array:
   • Update current segment length when encountering current maximum
   • Reset when encountering a new maximum or different value
   • Track the longest segment length
3. Return the maximum segment length

Complexity Analysis

Slightly more efficient as it finds the maximum and longest segment in a single pass.

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int max_val = INT_MIN;
        int curr_len = 0;
        int max_len = 0;
        
        for (int num : nums) {
            if (num > max_val) {
                // New maximum found
                max_val = num;
                max_len = 1;
                curr_len = 1;
            } else if (num == max_val) {
                // Continue current segment
                curr_len++;
                max_len = max(max_len, curr_len);
            } else {
                // Reset current segment
                curr_len = 0;
            }
        }
        
        return max_len;
    }
};

class Solution {
    public int longestSubarray(int[] nums) {
        int max_val = Integer.MIN_VALUE;
        int curr_len = 0;
        int max_len = 0;
        
        for (int num : nums) {
            if (num > max_val) {
                max_val = num;
                max_len = 1;
                curr_len = 1;
            } else if (num == max_val) {
                curr_len++;
                max_len = Math.max(max_len, curr_len);
            } else {
                curr_len = 0;
            }
        }
        
        return max_len;
    }
}

class Solution:
    极客 longestSubarray(self, nums: List[int]) -> int:
        max_val = float('-inf')
        curr_len = 0
        max_len = 0
        
        for num in nums:
            if num > max_val:
                # New maximum found
                max_val = num
                max_len = 1
                curr_len = 1
            elif num == max_val:
                # Continue current segment
                curr_len += 1
                max_len = max(max_len, curr_len)
            else:
                # Reset current segment
                curr_len = 0
                
        return max_len

Frequently Asked Questions