2419. Longest Subarray With Maximum Bitwise AND

Description

The problem requires finding the longest subarray where the maximum bitwise AND value is consistent across the subarray. The task is to calculate this maximum bitwise AND value from the given array and find the longest contiguous subarray where all elements are equal to this maximum value.

Intuition

The main idea behind solving this problem is to first identify the maximum value that can be obtained via bitwise AND in the array. Once the maximum value is found, the next step is to iterate through the array and find the longest sequence of consecutive elements that are equal to this maximum value.

Approach

1. Find the Maximum Value: Start by finding the maximum value in the array as this will be the value we're interested in.
2. Iterate through the Array: Traverse through the array to check how long the sequence of numbers equal to the maximum value continues. Keep track of the length of these sequences and update the result with the maximum length found.
3. Return the Result: The longest contiguous subarray with the maximum bitwise AND value is stored and returned at the end.

Complexity

Time Complexity:

O(n), where n is the number of elements in the input array. This is due to the need to iterate through the array twice, once to find the maximum value and once to find the longest subarray.

Space Complexity:

O(1) since only a few variables are used for counting and comparison, making the space usage constant.

Code

C++

class Solution {
public:
    int longestSubarray(vector& nums) {
        int maxBitwiseAnd = *max_element(nums.begin(), nums.end());
        int maxi = 1;
        int count = 0;
        int i = 0;

        while (i < nums.size()) {
            if (nums[i] == maxBitwiseAnd) {
                while (i < nums.size() && nums[i] == maxBitwiseAnd) {
                    count++;
                    i++;
                }
                maxi = max(maxi, count);
                count = 0;
            } else {
                i++;
            }
        }

        return maxi;
    }
};

Python

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        maxBitwiseAnd = max(nums)
        maxi = 1
        count = 0
        i = 0

        while i < len(nums):
            if nums[i] == maxBitwiseAnd:
                while i < len(nums) and nums[i] == maxBitwiseAnd:
                    count += 1
                    i += 1
                maxi = max(maxi, count)
                count = 0
            else:
                i += 1

        return maxi

Java

class Solution {
    public int longestSubarray(int[] nums) {
        int maxBitwiseAnd = Integer.MIN_VALUE;
        for (int num : nums) {
            maxBitwiseAnd = Math.max(maxBitwiseAnd, num);
        }

        int maxi = 1;
        int count = 0;
        int i = 0;

        while (i < nums.length) {
            if (nums[i] == maxBitwiseAnd) {
                while (i < nums.length && nums[i] == maxBitwiseAnd) {
                    count++;
                    i++;
                }
                maxi = Math.max(maxi, count);
                count = 0;
            } else {
                i++;
            }
        }

        return maxi;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function (nums) {
    let maxBitwiseAnd = Math.max(...nums);
    let maxi = 1;
    let count = 0;
    let i = 0;

    while (i < nums.length) {
        if (nums[i] === maxBitwiseAnd) {
            while (i < nums.length && nums[i] === maxBitwiseAnd) {
                count++;
                i++;
            }
            maxi = Math.max(maxi, count);
            count = 0;
        } else {
            i++;
        }
    }

    return maxi;
};