2401.Longest_Nice_Subarray(Medium).md

2401. Longest Nice Subarray (Medium)

Date and Time: Mar 18, 2025 (EST)

Link: https://leetcode.com/problems/longest-nice-subarray

Question:

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 <= 10^5

• 1 <= nums[i] <= 10^9

Walk-through:

We can use sliding window to save subarray with variable past, we use OR operation on past to remember which bit is 1. Then for current nums[r] we use it to compare with past by AND operation, if the result is not 0, means we have common bit, so we can start shrinking the sliding window by removing nums[l] by XOR operation.

Python Solution:

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        # Maintain a sliding window of all working ints on a variable
        # Perform & to check if we have common set bit with all previous ints or not
        # If we have common bit, shrink the sliding window from the left by performing XOR. Otherwise, update past by OR

        # TC: O(n), n=len(nums), SC: O(1)
        ans = 1
        l = 0
        past = 0
        for r in range(len(nums)):
            # Check if current int has common bit with past
            while nums[r] & past != 0:
                # Shrink the sliding window by XOR to remove bits
                past ^= nums[l]
                l += 1
            # Update past by OR
            past |= nums[r]
            ans = max(ans, r-l+1)
        return ans

Time Complexity: $O(n)$
Space Complexity: $O(1)$