Longest Nice Subarray solution and explanation
Google
9 more videos on this problem
Longest Nice Subarray | Brute Force | Better | Optimal | Dry Runs | Leetcode 2401 | codestorywithMIKcodestorywithMIK · 37:39 · 15K views
Longest Nice Subarray - Leetcode 2401 - PythonNeetCodeIO · 16:50 · 13K views
Leetcode 2401. Longest Nice Subarray | Weekly Contest 2401.Code with Alisha · 19:54 · 8K views
Longest Nice Subarray | Leetcode 2401Techdose · 19:31 · 6K views
2401. Longest Nice Subarray | Leetcode Weekly Contest 309 | LeetCode 2401Bro Coders · 14:43 · 6K views
2401. Longest Nice Subarray | leetcode daily challenge | dsa | shashcodeShashCode · 13:37 · 3K views
Leetcode 2401 Longest Nice Subarray | Sliding Window & Bit Manipulation | Coding Decoded SDE sheetCoding Decoded · 16:51 · 2K views
2401. Longest Nice Subarray (Leetcode Medium)Programming Live with Larry · 6:59 · 1K views
【每日一题】LeetCode 2401. Longest Nice SubarrayHuifeng Guan · 14:39 · 610 views
Longest Nice Subarray | Leetcode 2401Code with Siddhant · 6:56 · 210 views
The problem
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] <= 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
def longestNiceSubarray(nums):
start, mask, max_len = 0, 0, 1
for end in range(len(nums)):
while (mask & nums[end]) != 0:
mask ^= nums[start]
start += 1
mask |= nums[end]
max_len = max(max_len, end - start + 1)
return max_len
nums = [1, 3, 8, 48, 10]
print(longestNiceSubarray(nums))public class Main {
public static int longestNiceSubarray(int[] nums) {
int start = 0, mask = 0, maxLen = 1;
for (int end = 0; end < nums.length; end++) {
while ((mask & nums[end]) != 0) {
mask ^= nums[start++];
}
mask |= nums[end];
maxLen = Math.max(maxLen, end - start + 1);
}
return maxLen;
}
public static void main(String[] args) {
int[] nums = {1, 3, 8, 48, 10};
System.out.println(longestNiceSubarray(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int longestNiceSubarray(vector<int>& nums) {
int start = 0, mask = 0, maxLen = 1;
for (int end = 0; end < nums.size(); ++end) {
while ((mask & nums[end]) != 0) {
mask ^= nums[start++];
}
mask |= nums[end];
maxLen = max(maxLen, end - start + 1);
}
return maxLen;
}
int main() {
vector<int> nums = {1, 3, 8, 48, 10};
cout << longestNiceSubarray(nums) << endl;
return 0;
}function longestNiceSubarray(nums) {
let start = 0, mask = 0, maxLen = 1;
for (let end = 0; end < nums.length; end++) {
while ((mask & nums[end]) !== 0) {
mask ^= nums[start++];
}
mask |= nums[end];
maxLen = Math.max(maxLen, end - start + 1);
}
return maxLen;
}
let nums = [1, 3, 8, 48, 10];
console.log(longestNiceSubarray(nums));#include <stdio.h>
#include <stdlib.h>
int longestNiceSubarray(int* nums, int numsSize) {
int start = 0, mask = 0, maxLen = 1;
for (int end = 0; end < numsSize; end++) {
while ((mask & nums[end]) != 0) {
mask ^= nums[start++];
}
mask |= nums[end];
if ((end - start + 1) > maxLen)
maxLen = end - start + 1;
}
return maxLen;
}
int main() {
int nums[] = {1, 3, 8, 48, 10};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", longestNiceSubarray(nums, numsSize));
return 0;
}using System;
public class Solution {
public int LongestNiceSubarray(int[] nums) {
int start = 0, mask = 0, maxLen = 1;
for (int end = 0; end < nums.Length; end++) {
while ((mask & nums[end]) != 0) {
mask ^= nums[start++];
}
mask |= nums[end];
maxLen = Math.Max(maxLen, end - start + 1);
}
return maxLen;
}
public static void Main(string[] args) {
int[] nums = {1, 3, 8, 48, 10};
Solution solution = new Solution();
Console.WriteLine(solution.LongestNiceSubarray(nums));
}
}This Python implementation uses a similar approach with two pointers and a bitmask to ensure the subarray is nice. The start pointer advances when the subarray becomes non-nice due to a new element.
Time Complexity: O(n), given n is the length of nums.
Space Complexity: O(1).
Approach 2: Brute Force with Optimization
def longestNiceSubarray(nums):
max_len = 1
for i in range(len(nums)):
current_mask = nums[i]
for j in range(i + 1, len(nums)):
if current_mask & nums[j]:
break
current_mask |= nums[j]
max_len = max(max_len, j - i + 1)
return max_len
nums = [1, 3, 8, 48, 10]
print(longestNiceSubarray(nums))public class Main {
public static int longestNiceSubarray(int[] nums) {
int maxLen = 1;
for (int i = 0; i < nums.length; i++) {
int currentMask = nums[i];
for (int j = i + 1; j < nums.length; j++) {
if ((currentMask & nums[j]) != 0) break;
currentMask |= nums[j];
maxLen = Math.max(maxLen, j - i + 1);
}
}
return maxLen;
}
public static void main(String[] args) {
int[] nums = {1, 3, 8, 48, 10};
System.out.println(longestNiceSubarray(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int longestNiceSubarray(vector<int>& nums) {
int maxLen = 1;
for (int i = 0; i < nums.size(); ++i) {
int currentMask = nums[i];
for (int j = i + 1; j < nums.size(); ++j) {
if ((currentMask & nums[j]) != 0) break;
currentMask |= nums[j];
maxLen = max(maxLen, j - i + 1);
}
}
return maxLen;
}
int main() {
vector<int> nums = {1, 3, 8, 48, 10};
cout << longestNiceSubarray(nums) << endl;
return 0;
}function longestNiceSubarray(nums) {
let maxLen = 1;
for (let i = 0; i < nums.length; i++) {
let currentMask = nums[i];
for (let j = i + 1; j < nums.length; j++) {
if ((currentMask & nums[j]) !== 0) break;
currentMask |= nums[j];
maxLen = Math.max(maxLen, j - i + 1);
}
}
return maxLen;
}
let nums = [1, 3, 8, 48, 10];
console.log(longestNiceSubarray(nums));#include <stdio.h>
#include <stdbool.h>
int longestNiceSubarray(int* nums, int numsSize) {
int maxLen = 1;
for (int i = 0; i < numsSize; i++) {
int currentMask = nums[i];
for (int j = i + 1; j < numsSize; j++) {
if ((currentMask & nums[j]) != 0) break;
currentMask |= nums[j];
maxLen = (j - i + 1 > maxLen) ? j - i + 1 : maxLen;
}
}
return maxLen;
}
int main() {
int nums[] = {1, 3, 8, 48, 10};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", longestNiceSubarray(nums, numsSize));
return 0;
}using System;
public class Solution {
public int LongestNiceSubarray(int[] nums) {
int maxLen = 1;
for (int i = 0; i < nums.Length; i++) {
int currentMask = nums[i];
for (int j = i + 1; j < nums.Length; j++) {
if ((currentMask & nums[j]) != 0) break;
currentMask |= nums[j];
maxLen = Math.Max(maxLen, j - i + 1);
}
}
return maxLen;
}
public static void Main(string[] args) {
int[] nums = {1, 3, 8, 48, 10};
Solution solution = new Solution();
Console.WriteLine(solution.LongestNiceSubarray(nums));
}
}By iterating through each index and trying to expand the subarray, this Python implementation checks niceness with nested loops and short-circuits when non-nice conditions arise.
Time Complexity: O(n^2), inspects potential subarrays interactively.
Space Complexity: O(1), additional usage is minimal and temporary.
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).
function longestNiceSubarray(nums: number[]): number {
let [ans, mask] = [0, 0];
for (let l = 0, r = 0; r < nums.length; ++r) {
while (mask & nums[r]) {
mask ^= nums[l++];
}
mask |= nums[r];
ans = Math.max(ans, r - l + 1);
}
return ans;
}func longestNiceSubarray(nums []int) (ans int) {
mask, l := 0, 0
for r, x := range nums {
for mask&x != 0 {
mask ^= nums[l]
l++
}
mask |= x
ans = max(ans, r-l+1)
}
return
}impl Solution {
pub fn longest_nice_subarray(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mut mask = 0;
let mut l = 0;
for (r, &x) in nums.iter().enumerate() {
while mask & x != 0 {
mask ^= nums[l];
l += 1;
}
mask |= x;
ans = ans.max((r - l + 1) as i32);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Bitwise AND | Time Complexity: O(n), given n is the length of |
| Brute Force with Optimization | Time Complexity: O(n^2), inspects potential subarrays interactively. |
| Two Pointers | – |
Complexity analysis
| 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 |
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.