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] <= 109The 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
L10. Count number of Nice subarrays | 2 Pointers and Sliding Window Playlist • take U forward • 98,734 views views
Watch 9 more video solutions →Practice Longest Nice Subarray with our built-in code editor and test cases.
Practice on FleetCode