Jobs

Interviews

Discussions

Longest Nice Subarray

Medium

Asked by:

More companies

33 views

Topics:

ArraysTwo PointersSliding WindowsBit Manipulation

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 <= 10⁵
1 <= nums[i] <= 10⁹

Try coding it in LeetCode

Longest Nice Subarray

Medium

Asked by:

33 views

Topics:

ArraysTwo PointersSliding WindowsBit Manipulation

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 <= 10⁵
1 <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Can I assume they are non-negative?
What should I return if the input array is empty or null?
If there are multiple longest 'nice' subarrays of the same length, can I return any one of them?
Is the input array guaranteed to have at least one element?
Could you define 'nice' more formally, perhaps in terms of the bitwise AND operation on the subarray elements?

Brute Force Solution

Approach

The brute force approach is like trying out every single possibility, no matter how long it takes. For this particular puzzle, we examine every possible consecutive set of numbers to see if it meets our condition.

Here's how the algorithm would work step-by-step:

First, look at just the very first number in the list by itself.
Then, consider the first two numbers together as a set.
Next, check the first three numbers together, and so on, until you include all the numbers in the list.
After checking all sets that start with the first number, move on to the second number.
Now, look at just the second number by itself, then the second and third numbers together, then the second, third, and fourth numbers together, and so on.
Keep doing this, sliding down the list one number at a time, and checking all possible sets that start at each position.
For each of these sets of numbers you check, determine whether or not the numbers within the set meet our special 'nice' condition.
Keep track of the longest 'nice' set of numbers you find as you go.
Once you have checked every possible set of numbers in the list, the longest 'nice' set that you kept track of is your answer.

Code Implementation

def longest_nice_subarray_brute_force(numbers):
    longest_subarray_length = 0

    for start_index in range(len(numbers)):
        for end_index in range(start_index, len(numbers)):
            current_subarray = numbers[start_index:end_index + 1]

            # Check if the current subarray is 'nice'.
            if is_nice(current_subarray):

                # Update the longest length if needed.
                longest_subarray_length = max(
                    longest_subarray_length, len(current_subarray)
                )

    return longest_subarray_length

def is_nice(subarray):
    if not subarray:
        return True

    bitwise_and = subarray[0]
    for i in range(1, len(subarray)):
        bitwise_and &= subarray[i]

    # If bitwise AND is zero, the subarray is nice.
    if bitwise_and != 0:
        return False

    seen_numbers = set()
    for number in subarray:

        # Numbers must be unique to be nice.
        if number in seen_numbers:
            return False
        seen_numbers.add(number)

    return True

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through all possible subarrays. The outer loop iterates from the first element to the last (n iterations). The inner loop, for each starting element, iterates to the end of the array, checking all possible subarrays starting from that element, with a maximum of n iterations. Checking the 'nice' property of each subarray takes O(1) time, making the dominant cost the nested loops. The total number of operations is proportional to n + (n-1) + (n-2) + ... + 1, which approximates to n * (n+1) / 2. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through all possible subarrays of the input array but does not use any auxiliary data structures to store intermediate subarrays or track visited elements. It only uses a few variables to keep track of the current subarray's start and end indices and the length of the longest nice subarray found so far. Since the space used by these variables is constant and independent of the input size N (where N is the number of elements in the input array), the space complexity is O(1).

Optimal Solution

Approach

The core idea is to maintain a "window" of numbers and slide it across the input. We keep track of the numbers currently in the window such that their bitwise AND is zero. This window grows and shrinks to maximize its length while maintaining the zero AND condition.

Here's how the algorithm would work step-by-step:

Start with an empty window at the beginning of the numbers.
Expand the window by adding the next number to the right.
Check if the bitwise AND of all numbers within the current window is equal to zero.
If the bitwise AND is NOT zero, shrink the window from the left by removing the leftmost number until the bitwise AND of the remaining numbers becomes zero.
Keep track of the largest window size you've seen so far. This represents the longest "nice" subarray.
Repeat steps 2-5, sliding the window across the entire input numbers until you have checked all possible windows.
The largest window size you kept track of is the length of the longest "nice" subarray.

Code Implementation

def longestNiceSubarray(numbers) -> int:

    max_length = 0
    current_and = 0
    left_index = 0

    for right_index, current_number in enumerate(numbers):

        # Expand the window and update bitwise AND.
        current_and |= current_number

        # Shrink the window until bitwise AND becomes zero.
        while current_and != 0:
            current_and ^= numbers[left_index]
            left_index += 1

            # This ensures the AND is calculated only for the nice subarray.

        max_length = max(max_length, right_index - left_index + 1)

    return max_length

Big(O) Analysis

Time Complexity

O(n) – The outer loop iterates through the input array of size n, representing the right boundary of the sliding window. The inner loop, which shrinks the window from the left, only executes when the bitwise AND of the window is non-zero. Each element is added to and removed from the window at most once, ensuring the amortized cost of the inner loop is O(1) per element. Therefore, the overall time complexity is determined by the single pass through the array, resulting in O(n).

Space Complexity

O(1) – The algorithm uses a sliding window approach with a fixed number of integer variables to store the current window's start and end indices and the maximum length encountered so far. No auxiliary data structures like arrays, lists, or hash maps that scale with the input size N (the number of elements in the input array) are used. Therefore, the space complexity remains constant regardless of the input size.

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no subarray can be formed.
Array with a single element	Return 1, as a single element subarray is always 'nice'.
Array with all elements being 0	The entire array is a nice subarray, so return the array's length.
Array with elements that individually satisfy the 'nice' property but combined do not	The sliding window approach will dynamically adjust the window size to maintain the 'nice' property.
Array contains large integers that could potentially lead to integer overflow during bitwise AND operations if not handled carefully	Use appropriate data types to avoid overflow, or perform the check modularly if the problem allows for it, although bitwise AND inherently mitigates overflow risk as values are always reduced.
Array with very long sequence where the running bitwise AND is always zero until the very end	The solution's sliding window should still efficiently identify the longest sequence, moving the left pointer to adjust the subarray.
Maximum array size close to memory limits	The solution should use space efficiently (O(1) space for bitwise AND solution) to avoid memory issues.
All elements in the input array are the maximum integer value	Bitwise AND operations between any numbers should still return a valid result because the numbers are integers and bitwise operations are defined on integers.

Empty input array

How to Handle:

Return 0 since no subarray can be formed.

Array with a single element

How to Handle:

Return 1, as a single element subarray is always 'nice'.

Array with all elements being 0

How to Handle:

The entire array is a nice subarray, so return the array's length.

Array with elements that individually satisfy the 'nice' property but combined do not

How to Handle:

The sliding window approach will dynamically adjust the window size to maintain the 'nice' property.

Array contains large integers that could potentially lead to integer overflow during bitwise AND operations if not handled carefully

How to Handle:

Use appropriate data types to avoid overflow, or perform the check modularly if the problem allows for it, although bitwise AND inherently mitigates overflow risk as values are always reduced.

Array with very long sequence where the running bitwise AND is always zero until the very end

How to Handle:

The solution's sliding window should still efficiently identify the longest sequence, moving the left pointer to adjust the subarray.

Maximum array size close to memory limits

How to Handle:

The solution should use space efficiently (O(1) space for bitwise AND solution) to avoid memory issues.

All elements in the input array are the maximum integer value

How to Handle:

Bitwise AND operations between any numbers should still return a valid result because the numbers are integers and bitwise operations are defined on integers.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Can I assume they are non-negative?
What should I return if the input array is empty or null?
If there are multiple longest 'nice' subarrays of the same length, can I return any one of them?
Is the input array guaranteed to have at least one element?
Could you define 'nice' more formally, perhaps in terms of the bitwise AND operation on the subarray elements?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, look at just the very first number in the list by itself.
Then, consider the first two numbers together as a set.
Next, check the first three numbers together, and so on, until you include all the numbers in the list.
After checking all sets that start with the first number, move on to the second number.
Now, look at just the second number by itself, then the second and third numbers together, then the second, third, and fourth numbers together, and so on.
Keep doing this, sliding down the list one number at a time, and checking all possible sets that start at each position.
For each of these sets of numbers you check, determine whether or not the numbers within the set meet our special 'nice' condition.
Keep track of the longest 'nice' set of numbers you find as you go.
Once you have checked every possible set of numbers in the list, the longest 'nice' set that you kept track of is your answer.

Code Implementation

def longest_nice_subarray_brute_force(numbers):
    longest_subarray_length = 0

    for start_index in range(len(numbers)):
        for end_index in range(start_index, len(numbers)):
            current_subarray = numbers[start_index:end_index + 1]

            # Check if the current subarray is 'nice'.
            if is_nice(current_subarray):

                # Update the longest length if needed.
                longest_subarray_length = max(
                    longest_subarray_length, len(current_subarray)
                )

    return longest_subarray_length

def is_nice(subarray):
    if not subarray:
        return True

    bitwise_and = subarray[0]
    for i in range(1, len(subarray)):
        bitwise_and &= subarray[i]

    # If bitwise AND is zero, the subarray is nice.
    if bitwise_and != 0:
        return False

    seen_numbers = set()
    for number in subarray:

        # Numbers must be unique to be nice.
        if number in seen_numbers:
            return False
        seen_numbers.add(number)

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty window at the beginning of the numbers.
Expand the window by adding the next number to the right.
Check if the bitwise AND of all numbers within the current window is equal to zero.
If the bitwise AND is NOT zero, shrink the window from the left by removing the leftmost number until the bitwise AND of the remaining numbers becomes zero.
Keep track of the largest window size you've seen so far. This represents the longest "nice" subarray.
Repeat steps 2-5, sliding the window across the entire input numbers until you have checked all possible windows.
The largest window size you kept track of is the length of the longest "nice" subarray.

Code Implementation

def longestNiceSubarray(numbers) -> int:

    max_length = 0
    current_and = 0
    left_index = 0

    for right_index, current_number in enumerate(numbers):

        # Expand the window and update bitwise AND.
        current_and |= current_number

        # Shrink the window until bitwise AND becomes zero.
        while current_and != 0:
            current_and ^= numbers[left_index]
            left_index += 1

            # This ensures the AND is calculated only for the nice subarray.

        max_length = max(max_length, right_index - left_index + 1)

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no subarray can be formed.
Array with a single element	Return 1, as a single element subarray is always 'nice'.
Array with all elements being 0	The entire array is a nice subarray, so return the array's length.
Array with elements that individually satisfy the 'nice' property but combined do not	The sliding window approach will dynamically adjust the window size to maintain the 'nice' property.
Array contains large integers that could potentially lead to integer overflow during bitwise AND operations if not handled carefully	Use appropriate data types to avoid overflow, or perform the check modularly if the problem allows for it, although bitwise AND inherently mitigates overflow risk as values are always reduced.
Array with very long sequence where the running bitwise AND is always zero until the very end	The solution's sliding window should still efficiently identify the longest sequence, moving the left pointer to adjust the subarray.
Maximum array size close to memory limits	The solution should use space efficiently (O(1) space for bitwise AND solution) to avoid memory issues.
All elements in the input array are the maximum integer value	Bitwise AND operations between any numbers should still return a valid result because the numbers are integers and bitwise operations are defined on integers.

Empty input array

How to Handle:

Return 0 since no subarray can be formed.

Array with a single element

How to Handle:

Return 1, as a single element subarray is always 'nice'.

Array with all elements being 0

How to Handle:

The entire array is a nice subarray, so return the array's length.

Array with elements that individually satisfy the 'nice' property but combined do not

How to Handle:

The sliding window approach will dynamically adjust the window size to maintain the 'nice' property.

Array contains large integers that could potentially lead to integer overflow during bitwise AND operations if not handled carefully

How to Handle:

Use appropriate data types to avoid overflow, or perform the check modularly if the problem allows for it, although bitwise AND inherently mitigates overflow risk as values are always reduced.

Array with very long sequence where the running bitwise AND is always zero until the very end

How to Handle:

The solution's sliding window should still efficiently identify the longest sequence, moving the left pointer to adjust the subarray.

Maximum array size close to memory limits

How to Handle:

The solution should use space efficiently (O(1) space for bitwise AND solution) to avoid memory issues.

All elements in the input array are the maximum integer value

How to Handle:

Bitwise AND operations between any numbers should still return a valid result because the numbers are integers and bitwise operations are defined on integers.