Longest Nice Subarray
Medium · Sliding Window · Array · Bit Manipulation · Sliding Window
Problem
You are given an array nums of positive integers. A contiguous subarray is nice when the bitwise AND of every pair of its elements at different positions is 0. In other words, no bit is set in more than one element of the subarray. Any subarray of length 1 is nice.
Return the length of the longest nice subarray.
Examples
Input: nums = [3,8,48,10] Output: 3
3, 8 and 48 share no set bit. 10 (binary 1010) shares bit 3 with 8, so it cannot join them.
Input: nums = [5,5] Output: 1
5 AND 5 is 5, so only single elements are nice.
Input: nums = [1,3,8,48,10] Output: 3
1 and 3 share bit 0. After 1 leaves, 3, 8 and 48 form the longest nice window.
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= nums[i] <= 10^9
Approaches
- Grow from every start, checking pairs — time O(n · w²), w <= 30, space O(w)
Follow-up
How long can a nice subarray be? Each element has at least one set bit and no bit can be shared, so a nice subarray holds at most 30 elements when values are below 2^30. That bounds the baseline at about 30 steps per start, and it is why the window never holds more than 30 elements.
Related problems
Start free on Cariara · Coding problems · System design studio
