2419. Longest Subarray With Maximum Bitwise AND

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.

In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
The maximum possible bitwise AND of a subarray is 3.
The longest subarray with that value is [3,3], so we return 2.

Example 2:

Input: nums = [1,2,3,4]
Output: 1
Explanation:
The maximum possible bitwise AND of a subarray is 4.
The longest subarray with that value is [4], so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Solutions

Solution 1: Brain Teaser

Thinking

Bitwise AND never increases a value, so the maximum AND of any subarray is the global maximum \(\textit{mx}\). A subarray AND equals \(\textit{mx}\) iff every element is \(\textit{mx}\).

The task is the longest run of \(\textit{mx}\). Find the maximum, then scan once for its longest streak.

Since the bitwise AND operation does not increase the number, the maximum value is the maximum value in the array.

The problem can be converted to finding the maximum number of consecutive occurrences of the maximum value in the array.

First, traverse the array \(\textit{nums}\) to find the maximum value \(\textit{mx}\), then traverse the array again to find the maximum number of consecutive occurrences of the maximum value. Finally, return this count.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRustJavaScriptC#PHP

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        mx = max(nums)
        ans = cnt = 0
        for x in nums:
            if x == mx:
                cnt += 1
                ans = max(ans, cnt)
            else:
                cnt = 0
        return ans

class Solution {
    public int longestSubarray(int[] nums) {
        int mx = Arrays.stream(nums).max().getAsInt();
        int ans = 0, cnt = 0;
        for (int x : nums) {
            if (x == mx) {
                ans = Math.max(ans, ++cnt);
            } else {
                cnt = 0;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int mx = ranges::max(nums);
        int ans = 0, cnt = 0;
        for (int x : nums) {
            if (x == mx) {
                ans = max(ans, ++cnt);
            } else {
                cnt = 0;
            }
        }
        return ans;
    }
};

func longestSubarray(nums []int) (ans int) {
    mx := slices.Max(nums)
    cnt := 0
    for _, x := range nums {
        if x == mx {
            cnt++
            ans = max(ans, cnt)
        } else {
            cnt = 0
        }
    }
    return
}

function longestSubarray(nums: number[]): number {
    const mx = Math.max(...nums);
    let [ans, cnt] = [0, 0];
    for (const x of nums) {
        if (x === mx) {
            ans = Math.max(ans, ++cnt);
        } else {
            cnt = 0;
        }
    }
    return ans;
}

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let mx = *nums.iter().max().unwrap();
        let mut ans = 0;
        let mut cnt = 0;

        for &x in nums.iter() {
            if x == mx {
                cnt += 1;
                ans = ans.max(cnt);
            } else {
                cnt = 0;
            }
        }

        ans
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function (nums) {
    const mx = Math.max(...nums);
    let [ans, cnt] = [0, 0];
    for (const x of nums) {
        if (x === mx) {
            ans = Math.max(ans, ++cnt);
        } else {
            cnt = 0;
        }
    }
    return ans;
};

public class Solution {
    public int LongestSubarray(int[] nums) {
        int mx = nums.Max();
        int ans = 0, cnt = 0;
        foreach (int x in nums) {
            if (x == mx) {
                ans = Math.Max(ans, ++cnt);
            } else {
                cnt = 0;
            }
        }
        return ans;
    }
}

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function longestSubarray($nums) {
        $mx = max($nums);
        $ans = 0;
        $cnt = 0;

        foreach ($nums as $x) {
            if ($x == $mx) {
                $ans = max($ans, ++$cnt);
            } else {
                $cnt = 0;
            }
        }

        return $ans;
    }
}

2419. Longest Subarray With Maximum Bitwise AND

Description

Solutions

Solution 1: Brain Teaser

Comments