LeetCode 2401 - Longest Nice Subarray

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Sliding Window

Solution

Problem Understanding

The problem gives an array of positive integers and asks for the length of the longest contiguous subarray that is considered "nice".

A subarray is nice when every pair of distinct elements inside it has a bitwise AND equal to 0. In other words, for any two different numbers in the subarray:

a & b == 0

This condition means the two numbers cannot share any set bit positions. If one number has a 1 in a particular binary position, every other number in the subarray must have 0 in that same position.

For example:

3  = 0011
8  = 1000
48 = 110000

None of these numbers overlap in their set bits, so every pairwise AND is 0.

The input array can contain up to 10^5 elements, and each value can be as large as 10^9. These constraints immediately suggest that an O(n^2) solution will likely be too slow, because checking all subarrays or all pairs inside subarrays would require billions of operations in the worst case.

The problem guarantees that all numbers are positive integers. This matters because we do not need to worry about negative number bit representations or sign bits.

Several edge cases are important:

Arrays of length 1, the answer is always 1.
Arrays where every pair conflicts, the answer remains 1.
Arrays where all numbers are mutually compatible, the answer becomes the entire array length.
Cases where conflicts appear far apart, requiring careful shrinking of the window.
Numbers with multiple set bits, because a conflict can happen in several positions simultaneously.

The key challenge is efficiently determining whether a growing subarray still satisfies the pairwise AND condition.

Approaches

Brute Force Approach

The most direct solution is to examine every possible subarray.

For each starting index, we expand the subarray one element at a time and check whether the newly formed subarray is still nice. To verify this, we would compare the new element against all previous elements in the current subarray using bitwise AND.

For example:

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

Starting from index 0:

[1] is valid
[1,3] is invalid because 1 & 3 != 0

Starting from index 1:

[3] is valid
[3,8] is valid
[3,8,48] is valid
[3,8,48,10] is invalid because 8 & 10 != 0

This approach is correct because it explicitly checks every possible subarray and verifies the required condition exactly.

However, it is too slow for the constraints. In the worst case:

There are O(n^2) subarrays.
Each validation may require up to O(n) pair checks.

This leads to O(n^3) time in the naive form, or O(n^2) with incremental optimization, both of which are still too expensive for n = 10^5.

Key Insight for the Optimal Solution

The important observation is that a nice subarray cannot contain overlapping set bits.

Suppose we maintain a sliding window that is currently nice. Because no two numbers share a set bit, we can combine all numbers in the window using bitwise OR:

window_mask = nums[left] | nums[left+1] | ... | nums[right]

Since no bits overlap, every set bit in window_mask belongs to exactly one number in the window.

Now consider adding a new number nums[right].

If:

window_mask & nums[right] == 0

then the new number shares no bits with any existing number in the window, so the window remains nice.

Otherwise, there is a conflict. We must shrink the window from the left until the conflict disappears.

This naturally leads to a sliding window approach where:

The window always remains valid.
We expand the right boundary greedily.
We shrink the left boundary only when necessary.

Because each element enters and leaves the window at most once, the algorithm runs in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(1)	Checks many subarrays repeatedly
Optimal Sliding Window	O(n)	O(1)	Uses bitmask properties and two pointers

Algorithm Walkthrough

Initialize two pointers, left and right, representing the current sliding window.
Maintain a variable called window_mask. This stores the bitwise OR of all elements currently inside the window.
Iterate through the array using right.
Before adding nums[right] into the window, check whether it conflicts with the current window:

window_mask & nums[right]

If the result is nonzero, some bit overlaps with an existing number in the window, so the subarray would no longer be nice. 5. While a conflict exists, remove elements from the left side of the window.

Since every bit inside a valid window belongs to exactly one element, we can safely remove a number using XOR:

window_mask ^= nums[left]

Then increment left. 6. Once the conflict disappears, add the new number into the mask:

window_mask |= nums[right]

Compute the current window length:

right - left + 1

Update the maximum answer if this window is larger. 8. Continue until all elements have been processed.

Why it works

The sliding window always maintains the invariant that no two numbers inside the window share a set bit. Therefore, the current window is always a valid nice subarray.

When a conflict appears, shrinking from the left removes conflicting bits until the invariant is restored. Because each element is added once and removed once, the algorithm processes the array efficiently while guaranteeing that every maximal valid window is considered.

Python Solution

from typing import List

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        left = 0
        window_mask = 0
        max_length = 0

        for right in range(len(nums)):
            while window_mask & nums[right] != 0:
                window_mask ^= nums[left]
                left += 1

            window_mask |= nums[right]

            current_length = right - left + 1
            max_length = max(max_length, current_length)

        return max_length

The implementation follows the sliding window algorithm directly.

The variable left stores the beginning of the current window. The loop variable right expands the window one element at a time.

window_mask stores the OR combination of all numbers currently inside the window. Because the window is always maintained as valid, no bits overlap among its elements.

The while loop handles conflicts. If the new number shares any bit with the current mask, elements are removed from the left side until the overlap disappears.

Removing uses XOR instead of recomputing the entire mask. This works because every set bit belongs to exactly one element in a valid window.

After the conflict is resolved, the new number is merged into the window using OR. Then the current window length is calculated and used to update the answer.

Go Solution

func longestNiceSubarray(nums []int) int {
    left := 0
    windowMask := 0
    maxLength := 0

    for right := 0; right < len(nums); right++ {
        for (windowMask & nums[right]) != 0 {
            windowMask ^= nums[left]
            left++
        }

        windowMask |= nums[right]

        currentLength := right - left + 1
        if currentLength > maxLength {
            maxLength = currentLength
        }
    }

    return maxLength
}

The Go implementation mirrors the Python solution closely.

Go uses explicit variable declarations and standard for loops instead of Python's range. Integer overflow is not a concern because the constraints fit comfortably inside Go's default integer type on LeetCode platforms.

The bitwise operations behave identically to Python because all values are positive integers.

Worked Examples

Example 1

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

Binary representations:

1  = 000001
3  = 000011
8  = 001000
48 = 110000
10 = 001010

Step	right	nums[right]	window_mask before	Conflict?	left after shrinking	window_mask after	Window	Max Length
1	0	1	0	No	0	1	[1]	1
2	1	3	1	Yes	1	3	[3]	1
3	2	8	3	No	1	11	[3,8]	2
4	3	48	11	No	1	59	[3,8,48]	3
5	4	10	59	Yes	3	58	[48,10]	3

Final answer:

Example 2

nums = [3,1,5,11,13]

Binary representations:

Step	right	nums[right]	window_mask before	Conflict?	left after shrinking	window_mask after	Window	Max Length
1	0	3	0	No	0	3	[3]	1
2	1	1	3	Yes	1	1	[1]	1
3	2	5	1	Yes	2	5	[5]	1
4	3	11	5	Yes	3	11	[11]	1
5	4	13	11	Yes	4	13	[13]	1

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element enters and leaves the sliding window at most once
Space	O(1)	Only a few integer variables are used

The time complexity is linear because both pointers move only forward. Although there is a nested while loop, every element can be removed from the window only once across the entire execution.

The space complexity is constant because the algorithm stores only a few integer variables regardless of input size.

Test Cases

from typing import List

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        left = 0
        window_mask = 0
        max_length = 0

        for right in range(len(nums)):
            while window_mask & nums[right]:
                window_mask ^= nums[left]
                left += 1

            window_mask |= nums[right]
            max_length = max(max_length, right - left + 1)

        return max_length

sol = Solution()

assert sol.longestNiceSubarray([1,3,8,48,10]) == 3  # provided example
assert sol.longestNiceSubarray([3,1,5,11,13]) == 1  # every pair conflicts
assert sol.longestNiceSubarray([1]) == 1  # single element array
assert sol.longestNiceSubarray([1,2,4,8]) == 4  # all powers of two
assert sol.longestNiceSubarray([7,7,7]) == 1  # identical overlapping numbers
assert sol.longestNiceSubarray([1,2,3,4]) == 2  # partial overlap
assert sol.longestNiceSubarray([8,1,2,4]) == 4  # entire array valid
assert sol.longestNiceSubarray([5,1,8]) == 2  # shrinking required
assert sol.longestNiceSubarray([16,8,4,2,1]) == 5  # all non-overlapping bits
assert sol.longestNiceSubarray([1,2,1,2]) == 2  # alternating conflicts

Test	Why
`[1,3,8,48,10]`	Validates the primary example
`[3,1,5,11,13]`	Confirms answer can remain 1
`[1]`	Smallest valid input
`[1,2,4,8]`	Entire array forms a nice subarray
`[7,7,7]`	Every pair overlaps completely
`[1,2,3,4]`	Tests mixed valid and invalid expansions
`[8,1,2,4]`	Confirms long windows work correctly
`[5,1,8]`	Tests sliding window shrinking
`[16,8,4,2,1]`	Large fully valid window
`[1,2,1,2]`	Repeated conflicts and pointer movement

Edge Cases

One important edge case is an array with only one element. Since subarrays of length 1 are always nice, the answer must be 1. Some implementations accidentally initialize the result incorrectly or fail to handle minimal input sizes properly. This implementation naturally handles the case because the first iteration creates a window of length 1.

Another important case occurs when every pair of numbers conflicts. For example:

[7,7,7]

Every number shares bits with every other number, so no valid subarray longer than 1 exists. The sliding window repeatedly shrinks back to a single element, ensuring the maximum length never exceeds 1.

A third tricky case involves long valid windows with no overlaps, such as:

[1,2,4,8,16]

Each number uses a unique bit position, so the entire array is valid. The algorithm correctly keeps expanding the window without shrinking, producing the full array length as the answer.

Another subtle edge case is when conflicts appear after several valid additions. For example:

[1,2,4,3]

The first three numbers coexist without issue, but 3 overlaps with both 1 and 2. The algorithm must repeatedly shrink the window until all conflicts disappear. The while loop ensures that every conflicting element is removed before the new number is added.