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.
The solution employs a sliding window approach with two pointers: start and end. Additionally, it uses a mask to store the bitwise OR of the current subarray. If extending the window to include nums[end] results in a non-nice subarray, the solution slides the start pointer to the right, updating the mask accordingly until the subarray becomes nice again.
Time Complexity: O(n), where n is the length of the input array, as each element is processed at most twice.
Space Complexity: O(1), as only a few extra variables are used.
This solution takes each element as a starting point and attempts to expand the subarray forward while maintaining a bitmask to check if the subarray remains nice. It breaks early when non-nice conditions occur.
Time Complexity: O(n^2), where n is the number of elements, as it creates all possible subarrays.
Space Complexity: O(1), only uses a few variables.
According to the problem description, the position of the binary 1 in each element of the subarray must be unique to ensure that the bitwise AND result of any two elements is 0.
Therefore, we can use two pointers, l and r, to maintain a sliding window such that the elements within the window satisfy the problem's conditions.
We use a variable mask to represent the bitwise OR result of the elements within the window. Next, we traverse each element of the array. For the current element x, if the bitwise AND result of mask and x is not 0, it means that the current element x has overlapping binary bits with the elements in the window. At this point, we need to move the left pointer l until the bitwise AND result of mask and x is 0. Then, we assign the bitwise OR result of mask and x to mask and update the answer ans = max(ans, r - l + 1).
After the traversal, return the answer ans.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Sliding Window with Bitwise AND | Time Complexity: O(n), where n is the length of the input array, as each element is processed at most twice. |
| Brute Force with Optimization | Time Complexity: O(n^2), where n is the number of elements, as it creates all possible subarrays. |
| Two Pointers | — |
| 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 |
Longest Nice Subarray | Brute Force | Better | Optimal | Dry Runs | Leetcode 2401 | codestorywithMIK • codestorywithMIK • 15,144 views views
Watch 9 more video solutions →Practice Longest Nice Subarray with our built-in code editor and test cases.
Practice on FleetCode