Longest Nice Subarray

Medium
738.

Longest Nice Subarray

Longest Nice Subarray is a medium coding problem on arrays, bit manipulation and sliding window, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestNiceSubarray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Nice Subarray — Solution in Python, Java & C++

Longest Nice Subarray solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Nice Subarray is a medium coding problem on arrays, bit manipulation and sliding window, asked in Amazon, Google and Uber interviews.

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

Hints for Longest Nice Subarray

  1. Hint 1

    Pairwise disjoint bits is the same as saying the OR of the window has exactly as many bits as the elements contribute — no overlap.

  2. Hint 2

    Keep a running OR of the window. A new element fits exactly when used AND nums[right] is zero.

  3. Hint 3

    When it does not fit, drop elements from the left, XOR-ing each out of the running OR.

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

Java

public static int longestNiceSubarray(int[] nums) {
    int used = 0, left = 0, best = 0;
    for (int right = 0; right < nums.length; right++) {
        while ((used & nums[right]) != 0) {
            used ^= nums[left];
            left++;
        }
        used |= nums[right];
        best = Math.max(best, right - left + 1);
    }
    return best;
}

C++

int longestNiceSubarray(vector<int>& nums) {
    int used = 0, left = 0, best = 0;
    for (int right = 0; right < (int) nums.size(); right++) {
        while (used & nums[right]) {
            used ^= nums[left];
            left++;
        }
        used |= nums[right];
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation