Problem Informations

• Problem Index: 2401
• Problem Link: Longest Nice Subarray
• Topics: Array, Bit Manipulation, Sliding Window

Problem 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 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$

Intuition

The problem requires finding the length of the longest subarray where the bitwise AND of every pair of elements at different positions is zero. This condition ensures that no two numbers in the chosen subarray share a common set bit in the binary representation. The challenge is to efficiently manage overlapping elements to ensure they adhere to this constraint while maximizing subarray length.

Given the large constraints on the size of the input array, a brute-force approach that checks all subarrays would be computationally expensive. Therefore, a more efficient approach utilizing a sliding window to dynamically adjust the subarray is necessary.

Approach

We employ a sliding window approach with the assistance of bitwise operations to efficiently determine and extend the longest “nice” subarray. The algorithm proceeds as follows:

1. Initialize Variables: We start by initializing variables to keep track of the longest subarray length (longestLength), the current subarray length (currentLength), two pointers for the sliding window (left and right), and a variable to store the cumulative bitwise AND of the current subarray (currentBitwiseAnd).

2. Iterate Through Array: Begin iterating through the array with the right pointer. This pointer will attempt to expand the subarray by including new elements.

3. Adjust the Window: For each position of the right pointer:

   • Check if including the current element at right maintains the “nice” property by ensuring that the bitwise AND of the current element and currentBitwiseAnd is zero.
   • If the condition is violated, increment the left pointer and update currentBitwiseAnd by removing the effect of the element at left until the condition is satisfied. This can be achieved by applying bitwise XOR on currentBitwiseAnd with the element at left, effectively excluding it from the window.

4. Update Current AND: After ensuring the subarray is “nice,” include the right element by updating currentBitwiseAnd with a bitwise OR operation.

5. Compute Maximum Length: Continuously track the maximum length of such a subarray seen so far by updating longestLength.

6. Return Result: After traversing the array, return the computed longestLength, which reflects the maximum length of a “nice” subarray found.

This approach efficiently manages the constraints of the problem while ensuring operations remain linear with respect to the input size, thus achieving the optimal performance required for this problem.

Code

C++

class Solution {
public:
    // Function to return the length of the longest nice subarray
    int longestNiceSubarray(vector<int>& nums) {
        int longestLength = 1; // Initialize longest length to 1 (minimum nice subarray)
        int currentLength = 1; // Current subarray length
        int left = 0; // Left pointer for the sliding window
        int right = 0; // Right pointer for the sliding window
        int currentBitwiseAnd = 0; // Current cumulative bitwise AND for the window
        int len = nums.size(); // Size of input array
        
        // Iterate through array using right pointer
        for (; right < len; right++) {
            // Adjust left pointer until current element can be added to a nice subarray
            while ((nums[right] & currentBitwiseAnd) != 0) {
                currentBitwiseAnd ^= nums[left++]; // Exclude the left element from current AND
            }
            currentBitwiseAnd |= nums[right]; // Include the current element in the current AND
            // Update the longest length with the current subarray length
            longestLength = max(longestLength, right - left + 1);
        }
        
        return longestLength; // Return the maximum length of a nice subarray found
    }
};

Python

class Solution:
    # Function to return the length of the longest nice subarray
    def longestNiceSubarray(self, nums):
        longestLength = 1  # Initialize longest length to 1 (minimum nice subarray)
        left = 0  # Left pointer for the sliding window
        right = 0  # Right pointer for the sliding window
        currentBitwiseAnd = 0  # Current cumulative bitwise AND for the window
        len_nums = len(nums)  # Size of input array
        
        # Iterate through array using right pointer
        for right in range(len_nums):
            # Adjust left pointer until current element can be added to a nice subarray
            while (nums[right] & currentBitwiseAnd) != 0:
                currentBitwiseAnd ^= nums[left]  # Exclude the left element from current AND
                left += 1
            currentBitwiseAnd |= nums[right]  # Include the current element in the current AND
            # Update the longest length with the current subarray length
            longestLength = max(longestLength, right - left + 1)
        
        return longestLength  # Return the maximum length of a nice subarray found

Complexity

• Time complexity: $O(n)$

  The algorithm leverages a sliding window technique with two pointers, left and right. The right pointer iterates over each element of the input array nums, which results in a loop that runs at most $n$ times, where $n$ is the length of the array. Within this loop, the left pointer only advances; it never goes back, thus both pointers combined will only move a total of $n$ steps across the array in the worst case. As a result, the overall time complexity of the algorithm is linear, $O(n)$.

• Space complexity: $O(1)$

  The space complexity of the algorithm is constant, $O(1)$, because the algorithm uses a fixed amount of additional space that does not depend on the size of the input array. The primary additional variables include integers such as longestLength, currentLength, left, right, currentBitwiseAnd, and len, which occupy a constant amount of space. No additional data structures are used.