Watch 10 video solutions for Longest Nice Subarray, a medium level problem involving Array, Bit Manipulation, Sliding Window. This walkthrough by codestorywithMIK has 15,144 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array nums consisting of positive integers.
We call a subarray of nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.
Return the length of the longest nice subarray.
A subarray is a contiguous part of an array.
Note that subarrays of length 1 are always considered nice.
Example 1:
Input: nums = [1,3,8,48,10] Output: 3 Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions: - 3 AND 8 = 0. - 3 AND 48 = 0. - 8 AND 48 = 0. It can be proven that no longer nice subarray can be obtained, so we return 3.
Example 2:
Input: nums = [3,1,5,11,13] Output: 1 Explanation: The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109Problem Overview: Given an integer array, find the length of the longest subarray where every pair of elements has a bitwise AND equal to 0. In other words, no two numbers in the subarray share a common set bit. The task is to identify the maximum-length contiguous window that satisfies this constraint.
Approach 1: Brute Force with Bit Optimization (O(n²) time, O(1) space)
Start each subarray at index i and extend it to the right while maintaining a bitmask representing the OR of elements in the current subarray. Before adding a new element nums[j], check if (mask & nums[j]) != 0. If this condition is true, the new number shares at least one bit with an existing element, so the subarray is no longer nice and you stop extending it. Otherwise update the mask using mask |= nums[j] and continue. This approach explicitly explores all valid starting points and grows the window greedily until a conflict occurs. Time complexity is O(n²) in the worst case with constant extra space.
Approach 2: Sliding Window with Bitwise AND Check (O(n) time, O(1) space)
A more efficient solution uses a sliding window combined with a bitmask. Maintain two pointers left and right and a mask storing the OR of elements inside the window. When adding nums[right], check (mask & nums[right]). If the result is non-zero, the new element shares bits with some value already in the window. Move left forward while removing elements from the mask using mask ^= nums[left] until the conflict disappears. Then include the new number with mask |= nums[right] and update the maximum window size. Each element enters and leaves the window at most once, producing O(n) time and O(1) extra space.
This works because every number contributes a unique set of bits in a valid window. The mask effectively tracks which bits are currently occupied. Whenever two numbers attempt to share a bit, the window shrinks until that overlap disappears. The technique is a practical combination of bit manipulation and array traversal.
Recommended for interviews: The sliding window with a bitmask is the expected solution. Interviewers want to see recognition that overlapping bits create conflicts and that the window can be adjusted dynamically. Mentioning the brute force approach first shows you understand the constraint clearly, but implementing the linear-time sliding window demonstrates stronger algorithmic thinking and familiarity with bitwise operations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Bit Optimization | O(n²) | O(1) | Useful for understanding the constraint and validating the bit conflict rule |
| Sliding Window with Bitmask | O(n) | O(1) | Optimal solution for large arrays and typical interview expectations |