Skip to main content
Talentd

Longest Nice Subarray - Solution & Explanation

MediumArrayBit ManipulationSliding Window20 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109

Approach Overview

Problem 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 1: Sliding Window with Bitwise AND

This approach uses a sliding window technique to efficiently find the longest nice subarray. It starts with two pointers, `start` and `end`, both initialized at the beginning of the array. The sliding window maintains a bitmask representing the current subarray. If adding the next element to the window makes it non-nice, slide the start pointer to the right until the subarray becomes nice again.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 2: Brute Force with Optimization

This approach builds upon a brute force method but employs early termination to avoid unnecessary computations. Create all possible subarrays and compute their bitwise AND. Stop checking further when a subarray cannot be nice, thus reducing operations.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 3: Two Pointers

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).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), as only a few extra variables are used.

Brute Force with Optimization

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.

Two Pointersā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Bit OptimizationO(nĀ²)O(1)Useful for understanding the constraint and validating the bit conflict rule
Sliding Window with BitmaskO(n)O(1)Optimal solution for large arrays and typical interview expectations

Video Solution

Longest Nice Subarray | Brute Force | Better | Optimal | Dry Runs | Leetcode 2401 | codestorywithMIK ā€¢ codestorywithMIK ā€¢ 15,868 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Longest Nice Subarray easy or hard?
Longest Nice Subarray is rated Medium difficulty. The challenge is recognizing that overlapping bits define the constraint and that a sliding window with bitwise operations can enforce it efficiently.
Longest Nice Subarray Python/Java solution
Python and Java implementations follow the same sliding window logic: maintain a mask, expand the right pointer, and shrink the left pointer when overlapping bits appear. The algorithm stays O(n) time with constant extra space in both languages.
How to solve Longest Nice Subarray in O(n)?
Use two pointers and a bitmask representing the OR of numbers in the current window. For each new element, check if mask & nums[right] is non-zero. If so, move the left pointer and remove elements from the mask until the conflict disappears. Then add the new element and update the maximum length.
What is the best approach for Longest Nice Subarray?
The most efficient approach uses a sliding window with a bitmask. Maintain a window of elements and track used bits with a mask. If a new number shares any bit with the current mask, shrink the window from the left until the conflict disappears. This method runs in O(n) time and O(1) space.
Is Longest Nice Subarray asked at Google/Amazon/Meta?
Problems combining sliding window and bit manipulation frequently appear in interviews at companies like Google, Amazon, and Meta. Longest Nice Subarray specifically tests the ability to manage bit conflicts efficiently in a linear scan.
What data structure is used in Longest Nice Subarray?
The key structure is a bitmask stored in an integer to represent which bits are currently present in the window. The algorithm also uses the sliding window technique with two pointers over the array.
What is the time complexity of Longest Nice Subarray?
The optimal sliding window solution runs in O(n) time because each element enters and leaves the window at most once. Space complexity is O(1) since only a single integer bitmask is used to track active bits.

Ready to solve this problem?

Practice Longest Nice Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Bitwise AND of Numbers Range

Next

Bitwise ORs of Subarrays