Leetcode 2419: Longest Subarray With Maximum Bitwise AND

Input: You are given an array of integers nums of size n.

Example: nums = [5, 3, 7, 7, 2]

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^6

Output: Return the length of the longest contiguous subarray that has the maximum possible bitwise AND value.

Example: Output: 2

Constraints:

Goal: Identify the subarray with the highest possible bitwise AND and return the length of the longest one.

Steps:

• 1. Find the maximum number in the array.

• 2. Traverse the array and track the longest contiguous subarray where the bitwise AND of the subarray equals the maximum value found.

• 3. Return the length of this subarray.

Goal: The solution should handle arrays with up to 100,000 elements and individual values as large as 1,000,000.

Steps:

• The number of elements (n) can be as large as 100,000.

• Each element in the array is between 1 and 1,000,000.

Assumptions:

• The array will always contain at least one element.

• Input: Input: nums = [5, 3, 7, 7, 2]

• Explanation: The maximum bitwise AND is 7, and the longest subarray with this value is [7, 7], which has length 2.

Approach: The solution involves identifying the maximum number in the array, and then checking for the longest contiguous subarray where the bitwise AND equals this maximum value.

Observations:

• The highest possible AND value will be the maximum element in the array.

• We need to focus on the contiguous subarrays that contain only this maximum value.

• We can solve this problem by iterating through the array to track the longest sequence of the maximum number.

Steps:

• 1. Identify the maximum value in the array.

• 2. Iterate through the array to find the longest contiguous subarray of this maximum value.

• 3. Track the length of the current subarray and update the maximum length if necessary.

• 4. Return the maximum length.

Empty Inputs:

• The problem guarantees at least one element in the array, so this case will not occur.

Large Inputs:

• The solution should efficiently handle large arrays (up to 100,000 elements).

Special Values:

• If all elements in the array are the same, the entire array is the subarray with the maximum bitwise AND.

Constraints:

• Ensure the solution handles arrays with up to 100,000 elements.

int longestSubarray(vector<int>& nums) {
    int x = *max_element(nums.begin(), nums.end());
    int len = 0, ans = 0;
    for(int ele: nums) {
        if(ele == x) {
            ans = max(ans, ++len);
        } else len = 0;
    }
    return ans;
}

1 : Function Declaration

int longestSubarray(vector<int>& nums) {

This line defines the function 'longestSubarray', which takes a vector of integers (nums) as input and returns an integer representing the length of the longest subarray of consecutive maximum values.

2 : Find Maximum Element

    int x = *max_element(nums.begin(), nums.end());

This line finds the maximum element 'x' in the vector 'nums' using the 'max_element' function, which returns an iterator pointing to the largest element.

3 : Variable Initialization

    int len = 0, ans = 0;

Two variables are initialized: 'len' to track the current streak of consecutive maximum elements, and 'ans' to store the maximum streak length found.

4 : Loop

    for(int ele: nums) {

A loop is started to iterate over each element 'ele' in the 'nums' vector.

5 : Condition Check

        if(ele == x) {

This conditional checks if the current element 'ele' is equal to the maximum element 'x'.

6 : Update Streak

            ans = max(ans, ++len);

If the element is equal to the maximum value, 'len' is incremented, and 'ans' is updated to the larger of the current value of 'ans' or 'len'.

7 : Reset Streak

        } else len = 0;

If the element is not equal to the maximum value, the streak ('len') is reset to 0.

8 : Return

    return ans;

The function returns the value of 'ans', which holds the length of the longest contiguous subarray of maximum elements.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we are making two passes through the array: one to find the maximum and another to determine the longest subarray.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because we only need a few variables to keep track of the maximum value and the lengths.

Leetcode 2419: Longest Subarray With Maximum Bitwise AND

Explore →