Longest Nice Subarray

Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
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:

1
2
3
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 <= 10^5
1 <= nums[i] <= 10^9

Solution

Method 1 - Using Sliding Window

To solve the problem, we aim to find the longest subarray (contiguous sequence) of numbers such that the bitwise AND of any two numbers in different positions of the subarray is 0. This involves ensuring that no two numbers in the subarray have overlapping 1s in their binary representation.

Approach

Use a sliding window technique to maintain the longest possible nice subarray.
Keep a variable currMask that represents the cumulative bitwise OR of the elements in the current window (l to r).
As we expand the window by moving the right pointer r, check whether adding the element nums[r] violates the “nice” condition (i.e., whether (currMask & nums[r]) != 0).
If the condition is violated, shrink the window by incrementing the left pointer l and adjusting currMask.
Maintain and update the maximum length of the nice subarray (ans) along the way.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestNiceSubarray(int[] nums) {
        int l = 0;  // Left pointer
        int currMask = 0;  // Bitwise OR of current window
        int ans = 0;  // Maximum length of nice subarray
        
        for (int r = 0; r < nums.length; r++) {
            while ((currMask & nums[r]) != 0) {  // Condition violation
                currMask ^= nums[l];  // Remove nums[l] contribution
                l++;  // Shrink window
            }
            
            currMask |= nums[r];  // Add nums[r] contribution
            ans = Math.max(ans, r - l + 1);  // Update maximum length
        }
        
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        l: int = 0  # Left pointer
        currMask: int = 0  # Bitwise OR of current window
        ans: int = 0  # Maximum length of nice subarray
        
        for r, num in enumerate(nums):  # Right pointer iterates over nums
            while currMask & num:  # Condition violation
                currMask ^= nums[l]  # Remove nums[l] contribution
                l += 1  # Shrink window
            
            currMask |= num  # Add nums[r] contribution
            ans = max(ans, r - l + 1)  # Update maximum length
            
        return ans

Complexity

⏰ Time complexity: O(n), where n is the length of the array. The sliding window ensures that each element is processed at most twice (once when expanding the window, and once when contracting it). Hence the overall time is O(n).
🧺 Space complexity: O(1) as only a few variables are used.

Problem#

Examples#

Solution#

Method 1 - Using Sliding Window#

Approach#

Code#

Complexity#