Skip to content

2401. Longest Nice Subarray

Description

You are given an array nums consisting of positive integers.

We call a subarray of nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.

Return the length of the longest nice subarray.

A subarray is a contiguous part of an array.

Note that subarrays of length 1 are always considered nice.

 

Example 1:

Input: nums = [1,3,8,48,10]
Output: 3
Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions:
- 3 AND 8 = 0.
- 3 AND 48 = 0.
- 8 AND 48 = 0.
It can be proven that no longer nice subarray can be obtained, so we return 3.

Example 2:

Input: nums = [3,1,5,11,13]
Output: 1
Explanation: The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

Solutions

Solution 1: Two Pointers

Thinking

Checking every subarray for pairwise bitwise AND of zero is \(O(n^2)\) windows; \(n\le 10^5\) cannot pass. Scanning left from each right endpoint is still quadratic in the worst case.

Pairwise AND being zero means the \(1\)-bits of the numbers never overlap, so the bitwise OR of the window is a complete occupancy mask. Once a new value conflicts, elements must leave from the left until the conflict disappears, so the left endpoint only moves right.

Maintain the window OR in \(\textit{mask}\). Advance the right pointer; on conflict, XOR out the left value. Each index enters and leaves at most once, giving a linear longest nice window.

According to the problem description, the position of the binary \(1\) in each element of the subarray must be unique to ensure that the bitwise AND result of any two elements is \(0\).

Therefore, we can use two pointers, \(l\) and \(r\), to maintain a sliding window such that the elements within the window satisfy the problem's conditions.

We use a variable \(\textit{mask}\) to represent the bitwise OR result of the elements within the window. Next, we traverse each element of the array. For the current element \(x\), if the bitwise AND result of \(\textit{mask}\) and \(x\) is not \(0\), it means that the current element \(x\) has overlapping binary bits with the elements in the window. At this point, we need to move the left pointer \(l\) until the bitwise AND result of \(\textit{mask}\) and \(x\) is \(0\). Then, we assign the bitwise OR result of \(\textit{mask}\) and \(x\) to \(\textit{mask}\) and update the answer \(\textit{ans} = \max(\textit{ans}, r - l + 1)\).

After the traversal, return the answer \(\textit{ans}\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        ans = mask = l = 0
        for r, x in enumerate(nums):
            while mask & x:
                mask ^= nums[l]
                l += 1
            mask |= x
            ans = max(ans, r - l + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int longestNiceSubarray(int[] nums) {
        int ans = 0, mask = 0;
        for (int l = 0, r = 0; r < nums.length; ++r) {
            while ((mask & nums[r]) != 0) {
                mask ^= nums[l++];
            }
            mask |= nums[r];
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int ans = 0, mask = 0;
        for (int l = 0, r = 0; r < nums.size(); ++r) {
            while (mask & nums[r]) {
                mask ^= nums[l++];
            }
            mask |= nums[r];
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func longestNiceSubarray(nums []int) (ans int) {
    mask, l := 0, 0
    for r, x := range nums {
        for mask&x != 0 {
            mask ^= nums[l]
            l++
        }
        mask |= x
        ans = max(ans, r-l+1)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function longestNiceSubarray(nums: number[]): number {
    let [ans, mask] = [0, 0];
    for (let l = 0, r = 0; r < nums.length; ++r) {
        while (mask & nums[r]) {
            mask ^= nums[l++];
        }
        mask |= nums[r];
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn longest_nice_subarray(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut mask = 0;
        let mut l = 0;
        for (r, &x) in nums.iter().enumerate() {
            while mask & x != 0 {
                mask ^= nums[l];
                l += 1;
            }
            mask |= x;
            ans = ans.max((r - l + 1) as i32);
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public class Solution {
    public int LongestNiceSubarray(int[] nums) {
        int ans = 0, mask = 0;
        for (int l = 0, r = 0; r < nums.Length; ++r) {
            while ((mask & nums[r]) != 0) {
                mask ^= nums[l++];
            }
            mask |= nums[r];
            ans = Math.Max(ans, r - l + 1);
        }
        return ans;
    }
}

Comments