Get started

Longest Nice Subarray — Medium Problem & Solution

A subarray is nice when every pair of its elements has a bitwise AND of 0 — that is, no two elements share a set bit.

Problem statement

A subarray is nice when every pair of its elements has a bitwise AND of 0 — that is, no two elements share a set bit.

Return the length of the longest nice subarray. A single element is always nice.

Example 1

Input: nums = [1,3,8,48,10]
Output: 3
Explanation: [3,8,48] uses disjoint bit sets.

Example 2

Input: nums = [3,1,5,11,13]
Output: 1
Explanation: Every adjacent pair shares a bit.

Example 3

Input: nums = [1,2,4,8]
Output: 4

Constraints

  • 1 <= nums.length <= 100000
  • 1 <= nums[i] <= 1000000000

How to solve Longest Nice Subarray

Because the elements in a nice window have disjoint bits, their OR doubles as an exact record of which bits are taken — and XOR removes an element's bits cleanly, since no other element shares them.

Approach

  1. Sweep right across the array keeping used, the OR of the current window.
  2. While used & nums[right] is non-zero, remove nums[left] with used ^= nums[left] and advance left.
  3. OR nums[right] into used and record the window length.

Why it works

Within a nice window every bit belongs to at most one element, so used is a disjoint union and used ^ nums[left] removes exactly that element's bits. The window is nice precisely when each new element's bits are free, which the AND test checks in constant time.

Complexity

  • Time — O(n) — each index enters and leaves once
  • Space — O(1)

Pitfalls

  • Using used -= nums[left] happens to work only because the bits are disjoint; XOR states the intent and survives a refactor.
  • Checking only adjacent pairs is not enough — the condition is over every pair in the window.
  • The answer is at least 1, since a lone element has no pairs to violate the rule.

Reference solution

Python

from typing import List

def longestNiceSubarray(nums: List[int]) -> int:
    used = left = best = 0
    for right, x in enumerate(nums):
        while used & x:
            used ^= nums[left]
            left += 1
        used |= x
        best = max(best, right - left + 1)
    return best

JavaScript

var longestNiceSubarray = function(nums) {
    var used = 0, left = 0, best = 0;
    for (var right = 0; right < nums.length; right++) {
        while ((used & nums[right]) !== 0) {
            used ^= nums[left];
            left++;
        }
        used |= nums[right];
        if (right - left + 1 > best) best = right - left + 1;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue