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.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Sliding Window
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1000001 <= nums[i] <= 1000000000
Hints for Longest Nice Subarray
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.
Hint 2
Keep a running OR of the window. A new element fits exactly when
used AND nums[right]is zero.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
- Sweep
rightacross the array keepingused, the OR of the current window. - While
used & nums[right]is non-zero, removenums[left]withused ^= nums[left]and advanceleft. - OR
nums[right]intousedand 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 bestJava
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