LeetCode 2401. Longest Nice Subarray Solution in Java, C++, Python & More | Explanation + Code

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

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 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 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 mask and x is 0. Then, we assign the bitwise OR result of mask and x to mask and update the answer ans = max(ans, r - l + 1).

After the traversal, return the answer ans.

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

PythonJavaC++GoTypeScriptRustC#

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

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 } }(code-box)

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; } }(code-box)