Longest Nice Subarray

medium array bit manipulation sliding window

Problem

You are given an array of positive integers nums. A subarray is called "nice" if every pair of its elements has a bitwise AND equal to 0 — in other words, no two elements share a common set bit. Return the length of the longest nice subarray. A single element is always nice.

Inputnums = [1, 3, 8, 48, 10]

Output3

The subarray [3, 8, 48] is nice: 3 & 8 = 0, 3 & 48 = 0, and 8 & 48 = 0. No longer nice subarray exists, so the answer is 3.

nums (comma-separated)

def longest_nice_subarray(nums):
    best = l = mask = 0
    for r, x in enumerate(nums):
        while mask & x:
            mask ^= nums[l]
            l += 1
        mask |= x
        best = max(best, r - l + 1)
    return best

function longestNiceSubarray(nums) {
  let best = 0, l = 0, mask = 0;
  for (let r = 0; r < nums.length; r++) {
    while (mask & nums[r]) {
      mask ^= nums[l];
      l++;
    }
    mask |= nums[r];
    best = Math.max(best, r - l + 1);
  }
  return best;
}

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int best = 0, l = 0, mask = 0;
        for (int r = 0; r < nums.length; r++) {
            while ((mask & nums[r]) != 0) {
                mask ^= nums[l];
                l++;
            }
            mask |= nums[r];
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

int longestNiceSubarray(vector<int>& nums) {
    int best = 0, l = 0, mask = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        while (mask & nums[r]) {
            mask ^= nums[l];
            l++;
        }
        mask |= nums[r];
        best = max(best, r - l + 1);
    }
    return best;
}

Explanation

A subarray is "nice" when no two of its numbers share a set bit. The clever observation is that this condition for a whole window can be tracked with a single integer mask — the bitwise OR of every element currently inside the window. Because the window is nice, each set bit in mask comes from exactly one element, so mask behaves like a tidy set of "claimed" bits.

We slide a window with two pointers. The right pointer r walks forward and tries to admit nums[r]. Before adding it, we ask: does the new number collide with any bit already claimed? That is exactly the test mask & nums[r]. If it is non-zero, some earlier element shares a bit with nums[r], so the window cannot stay nice while keeping both.

To fix the collision we shrink from the left: remove nums[l] from the mask with mask ^= nums[l] (XOR clears the bits that element contributed), advance l, and re-check. We keep dropping elements until mask & nums[r] becomes 0. Now it is safe to fold the new number in with mask |= nums[r] and record the window length r - l + 1 if it beats the best so far.

Example: nums = [1, 3, 8, 48, 10]. We absorb 1 (mask = 1) and 3 — but 3 shares bit 0 with 1, so we drop 1, leaving the window [3] with mask = 3. Then 8 and 48 have no overlap with 3, growing the window to [3, 8, 48] of length 3. Finally 10 collides with the bit-1 inside 3, so the left side trims down again. The longest nice window seen was length 3.

Every element is added to the mask once and removed at most once, so the two pointers each move forward only, giving linear time with constant extra space.

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