#2401

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Longest Nice Subarray

Find the length of the longest nice subarray where the bitwise AND of all pairs of elements in the subarray is zero.

Problem Statement

You are given an array of positive integers. A subarray is considered nice if the bitwise AND of every pair of distinct elements in the subarray is zero.

Return the length of the longest nice subarray that can be formed from the given array.

Examples

Example 1

Input: nums = [1,3,8,48,10]

Output: 3

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

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

Solution Approach

Sliding Window Approach

We use a sliding window to maintain a dynamic subarray and its corresponding bitwise AND. As we expand the window, we keep updating the AND until it no longer satisfies the condition. When the condition fails, shrink the window from the left side to re-establish validity.

Bitwise AND for Validity

For each element in the subarray, check if the bitwise AND with other elements results in zero. This ensures that no two elements in the subarray conflict. The sliding window ensures that only valid subarrays are considered for the maximum length.

Efficiency with Running State

Instead of recalculating the bitwise AND for the entire window repeatedly, maintain a running AND as you move the window across the array. This reduces time complexity and ensures that we only check the subarray’s validity incrementally.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The solution runs in linear time O(n) because we only scan through the array once with the sliding window. We update the bitwise AND incrementally and perform constant-time operations on each element, ensuring space complexity remains O(1).

What Interviewers Usually Probe

Look for an understanding of sliding window with running state updates.
Expect explanations of bitwise operations and their role in ensuring the subarray's validity.
Test for clarity on maintaining the subarray's length while adjusting the window.

Common Pitfalls or Variants

Common pitfalls

Incorrect handling of subarrays with overlapping elements.
Misunderstanding the role of bitwise AND and not updating the state correctly.
Failing to shrink the window properly when a subarray becomes invalid.

Follow-up variants

Test with arrays where all elements are powers of 2.
Handle the case where no valid subarray can be formed.
Test with the minimum input size to check edge cases.

FAQ

What is the sliding window technique used in the Longest Nice Subarray problem?

The sliding window technique is used to maintain a dynamic subarray where elements are checked for validity using bitwise AND operations. As the window slides, invalid subarrays are removed efficiently.

How does bitwise AND help determine the validity of a subarray in this problem?

Bitwise AND ensures that no two elements in the subarray have overlapping bits. If the AND of any two elements is non-zero, the subarray is invalid.

What is the time complexity of the Longest Nice Subarray problem?

The time complexity is O(n), as the solution uses a sliding window to scan through the array once while maintaining a running AND state.

What is the maximum possible length of a nice subarray?

The maximum length depends on the array, but the sliding window approach ensures that we find the longest subarray with valid AND conditions efficiently.

How does GhostInterview help in solving this problem?

GhostInterview focuses on guiding you through efficient sliding window techniques, bitwise operations, and state management, making the solution process smoother and faster.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        ans = mask = l = 0
        for r, x in enumerate(nums):
            while mask & x:
                mask ^= nums[l]
                l += 1
            mask |= x
            ans = max(ans, r - l + 1)
        return ans

Continue Practicing

#2411 smallest subarrays with maximum bitwise or #2932 maximum strong pair xor i #2935 maximum strong pair xor ii