Longest Nice Subarray

Longest Nice Subarray

What is this problem about?

The Longest Nice Subarray interview question provides an array of positive integers. A subarray is defined as "nice" if the bitwise AND of every pair of elements within it is equal to 0. You need to return the length of the longest nice subarray. In simple terms, no two numbers in the subarray can have a 1 bit in the exact same binary position.

Why is this asked in interviews?

This problem is a brilliant fusion of Sliding Window mechanics and Bit Manipulation. Interviewers ask it to test if a candidate is comfortable with binary operators (AND, OR, XOR) and whether they can conceptualize bitwise collisions as a resource constraint. It reveals how well a candidate can optimize a window expansion using bit masks instead of nested loops.

Algorithmic pattern used

This problem perfectly fits the Sliding Window pattern combined with a Bitmask. We maintain a window_or variable that represents the combined bits of all numbers currently in our sliding window. When we try to add a new number, we check if (window_or & new_number) == 0. If it is 0, there are no overlapping bits! We include the number, update the mask using bitwise OR, and expand the window. If not, we shrink the window from the left, removing elements by using bitwise XOR (window_or ^= arr[left]).

Example explanation

Array: [1, 3, 8, 48, 10]

• num = 1 (binary 000001): window_or starts at 0. 0 & 1 = 0. Add 1. window_or becomes 1. Max length = 1.
• num = 3 (binary 000011): window_or is 1. 1 & 3 = 1 (collision!). We must shrink. We remove the left element (1). window_or ^= 1 makes it 0. Now add 3. window_or becomes 3.
• num = 8 (binary 001000): window_or is 3 (000011). 3 & 8 = 0. No collision! Add 8. window_or becomes 3 | 8 = 11 (001011). Max length = 2.
• num = 48 (binary 110000): window_or is 11. 11 & 48 = 0. No collision! Add 48. window_or becomes 11 | 48 = 59 (111011). Max length = 3. The nice subarray is [3, 8, 48].

Common mistakes candidates make

The most common mistake is attempting to check the bitwise AND of every possible pair in the window on every iteration ($O(N \times K^2)$ time). This fundamentally misses the property of the bitwise OR operator. Because all numbers are positive, the bitwise OR acts as a perfect "registry" of all bits currently in use. Another mistake is using subtraction (-) instead of XOR (^) to remove elements from the bitmask. While subtraction might work here because no bits overlap, XOR is the idiomatic and safe way to toggle bits off.

Interview preparation tip

To ace the Longest Nice Subarray coding problem, make sure you deeply understand how to use integers as sets (Bitmasks). Memorize the basic operations: OR (|) to add an item to the set, AND (&) to check for intersections, and XOR (^) to remove an item from the set. This will make advanced sliding window problems trivial.