We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Nice Subarray

Number: 2478

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Meta, Paytm

Problem Description

Given an array of positive integers, find the length of the longest contiguous subarray such that for every pair of distinct elements in the subarray, the bitwise AND is equal to 0.

Key Insights

  • The subarray is "nice" if no two numbers have any overlapping set bits (i.e. the bitwise AND of any two different elements is 0).
  • A sliding window approach is natural since the subarray must be contiguous.
  • Use a bitmask to keep track of the combined bits included in the current window.
  • When a new number conflicts (shares a common bit) with the current bitmask, slide the left end of the window until the conflict is resolved.

Space and Time Complexity

Time Complexity: O(n) - each element is processed at most twice (once when added and once when removed). Space Complexity: O(1) - only a few extra variables (bitmask, pointers) are used independent of input size.

Solution

We use the sliding window algorithm where two pointers (left and right) are maintained representing the current subarray. A bitmask (currBitmask) tracks the union of bits present in all numbers in the current window. For every new number at the right pointer, check if its bits conflict (i.e. there is any bit that is already set in currBitmask). If there is a conflict, move the left pointer rightwards, removing numbers from the bitmask until there is no conflict. Once the new number is inserted into the window (by updating the bitmask), update the maximum window length. This ensures that the current window always represents a "nice" subarray.

Code Solutions

# Python solution for Longest Nice Subarray
class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        # Initialize pointers and bitmask
        left = 0
        curr_bitmask = 0
        max_length = 0
        
        # Iterate through the array with right pointer
        for right in range(len(nums)):
            # While there is a conflict (common set bit) between curr_bitmask and nums[right]
            while (curr_bitmask & nums[right]) != 0:
                # Remove nums[left] from current bitmask by XORing (since numbers have non overlapping bits when valid)
                curr_bitmask ^= nums[left]
                left += 1
            # Add current number into the bitmask using bitwise OR
            curr_bitmask |= nums[right]
            # Calculate maximum window length so far
            max_length = max(max_length, right - left + 1)
        return max_length

# Note: XOR can safely remove a number since no two numbers share set bits if the window is nice.
← Back to All Questions