Jobs

Interviews

Discussions

Longest Subarray With Maximum Bitwise AND

Medium

Google

8 views

Topics:

ArraysBit Manipulation

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
The maximum possible bitwise AND of a subarray is 3.
The longest subarray with that value is [3,3], so we return 2.

Example 2:

Input: nums = [1,2,3,4]
Output: 1
Explanation:
The maximum possible bitwise AND of a subarray is 4.
The longest subarray with that value is [4], so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Longest Subarray With Maximum Bitwise AND

Medium

Google

8 views

Topics:

ArraysBit Manipulation

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
The maximum possible bitwise AND of a subarray is 3.
The longest subarray with that value is [3,3], so we return 2.

Example 2:

Input: nums = [1,2,3,4]
Output: 1
Explanation:
The maximum possible bitwise AND of a subarray is 4.
The longest subarray with that value is [4], so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

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 in the input array? Could the numbers be negative or zero?
What should I return if the input array is empty or null?
If there are multiple subarrays with the same maximum bitwise AND, should I return the length of the longest one, or just any one of them?
Is the input array guaranteed to contain at least one element?
Are there any memory constraints I should be aware of?

Brute Force Solution

Approach

To find the longest part of a group with the highest matching characteristic, the brute force method involves checking every single possible part. We calculate this matching characteristic for each part and keep track of the longest one that has the highest value we've seen so far.

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

Consider each single item in the group as a potential part.
Calculate the matching characteristic for that item.
Keep track of the highest matching characteristic found so far, and the length of the part that gave us that value.
Now, consider all possible pairs of consecutive items as a potential part.
Calculate the matching characteristic for this pair.
Compare it to the highest value we've found so far. If it's higher, update our highest value and the length of the part.
If it's the same, check if this part is longer than our current longest part. If it is, update our length value.
Repeat the same process, increasing the part's size by one each time, until we consider the entire group as one big part.
After checking all possible parts, the length we've stored represents the length of the longest part with the highest matching characteristic.

Code Implementation

def longest_subarray_with_maximum_bitwise_and_brute_force(numbers):
    maximum_bitwise_and = 0
    longest_subarray_length = 0

    for i in range(len(numbers)):
        current_bitwise_and = numbers[i]

        # Initialize subarray with a single element
        if current_bitwise_and > maximum_bitwise_and:
            maximum_bitwise_and = current_bitwise_and
            longest_subarray_length = 1
        elif current_bitwise_and == maximum_bitwise_and:
            longest_subarray_length = max(longest_subarray_length, 1)

        for j in range(i + 1, len(numbers)):
            current_bitwise_and &= numbers[j]

            # Found new maximum bitwise AND
            if current_bitwise_and > maximum_bitwise_and:
                maximum_bitwise_and = current_bitwise_and
                longest_subarray_length = j - i + 1

            # Found same maximum bitwise AND
            elif current_bitwise_and == maximum_bitwise_and:
                # Update length if current subarray is longer
                longest_subarray_length = max(longest_subarray_length, j - i + 1)

    return longest_subarray_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays of the input array of size n. The outer loop implicitly defines the starting point of the subarray, and the inner workings (implied by steps 4-8) determine the subarray's length. In the worst-case scenario, it will check all possible subarrays, which is proportional to the sum of integers from 1 to n (subarray lengths). This summation results in approximately n*(n+1)/2 operations. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The algorithm described uses a few variables to keep track of the highest matching characteristic found so far, and the length of the longest subarray with that characteristic. No additional data structures that scale with the input size N (where N is the length of the input group) are used; the algorithm operates in place. Therefore, the space complexity is constant, O(1).

Optimal Solution

Approach

The goal is to find the longest continuous section where every number in that section has the largest possible 'AND' value. We don't need to check all possible sections; instead, we can efficiently find the maximum 'AND' value and then focus only on sections containing numbers that match that value.

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

First, find the largest number in the entire group of numbers. This largest number will be our target 'AND' value.
Now, walk through the numbers one by one. If a number matches the target 'AND' value, start counting how many consecutive numbers also match that value.
If a number doesn't match the target, stop counting and remember how long the previous matching section was.
Keep doing this until you've checked all the numbers. The longest matching section you found is your answer.

Code Implementation

def longest_subarray_with_max_bitwise_and(numbers):
    max_number = max(numbers)

    max_and = max_number
    max_length = 0
    current_length = 0

    for number in numbers:
        # Check if the current number equals to max_and value
        if number == max_and:
            current_length += 1
        else:
            # If not, it breaks the current sequence.
            max_length = max(max_length, current_length)
            current_length = 0

    # Update one last time after the loop.
    max_length = max(max_length, current_length)
    return max_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm first iterates through the input array of size n to find the maximum element. Then, it iterates through the array again to identify consecutive subarrays where each element equals the maximum element. Both iterations are independent and visit each element in the array once. Therefore, the time complexity is dominated by two linear passes over the array, resulting in O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It stores the maximum AND value, the length of the current matching subarray, and the length of the longest matching subarray found so far. These variables take up a fixed amount of space, irrespective of the input array's size (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty array	Return 0, as there is no subarray.
Array with a single element	Return 1, as the single element is the longest subarray with the maximum bitwise AND (itself).
Array with all elements being 0	Return the length of the array because the bitwise AND of any subarray will be 0 which is the maximum possible AND value.
Array with all elements having the same value	Return the length of the array as any subarray will have the same maximum bitwise AND value.
Array with a very large number of elements (close to the maximum allowed size)	Ensure the solution uses an algorithm with acceptable time complexity (e.g., O(n)) to avoid timeouts.
Array with extremely large integer values that could cause integer overflow when calculating the bitwise AND (in some languages)	Use appropriate data types (e.g., long) or consider bitwise operations carefully to prevent overflow.
Array where no subarray has a bitwise AND greater than 0	The solution should correctly identify the elements with maximum value (which is 0 in this case) and return the length of subarray containing them.
Multiple subarrays have the same maximum length.	The algorithm should still return the correct (maximum) length, as only the length, not the subarray itself, is required.

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 in the input array? Could the numbers be negative or zero?
What should I return if the input array is empty or null?
If there are multiple subarrays with the same maximum bitwise AND, should I return the length of the longest one, or just any one of them?
Is the input array guaranteed to contain at least one element?
Are there any memory constraints I should be aware of?

Brute Force Solution

Approach

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

Consider each single item in the group as a potential part.
Calculate the matching characteristic for that item.
Keep track of the highest matching characteristic found so far, and the length of the part that gave us that value.
Now, consider all possible pairs of consecutive items as a potential part.
Calculate the matching characteristic for this pair.
Compare it to the highest value we've found so far. If it's higher, update our highest value and the length of the part.
If it's the same, check if this part is longer than our current longest part. If it is, update our length value.
Repeat the same process, increasing the part's size by one each time, until we consider the entire group as one big part.
After checking all possible parts, the length we've stored represents the length of the longest part with the highest matching characteristic.

Code Implementation

def longest_subarray_with_maximum_bitwise_and_brute_force(numbers):
    maximum_bitwise_and = 0
    longest_subarray_length = 0

    for i in range(len(numbers)):
        current_bitwise_and = numbers[i]

        # Initialize subarray with a single element
        if current_bitwise_and > maximum_bitwise_and:
            maximum_bitwise_and = current_bitwise_and
            longest_subarray_length = 1
        elif current_bitwise_and == maximum_bitwise_and:
            longest_subarray_length = max(longest_subarray_length, 1)

        for j in range(i + 1, len(numbers)):
            current_bitwise_and &= numbers[j]

            # Found new maximum bitwise AND
            if current_bitwise_and > maximum_bitwise_and:
                maximum_bitwise_and = current_bitwise_and
                longest_subarray_length = j - i + 1

            # Found same maximum bitwise AND
            elif current_bitwise_and == maximum_bitwise_and:
                # Update length if current subarray is longer
                longest_subarray_length = max(longest_subarray_length, j - i + 1)

    return longest_subarray_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find the largest number in the entire group of numbers. This largest number will be our target 'AND' value.
Now, walk through the numbers one by one. If a number matches the target 'AND' value, start counting how many consecutive numbers also match that value.
If a number doesn't match the target, stop counting and remember how long the previous matching section was.
Keep doing this until you've checked all the numbers. The longest matching section you found is your answer.

Code Implementation

def longest_subarray_with_max_bitwise_and(numbers):
    max_number = max(numbers)

    max_and = max_number
    max_length = 0
    current_length = 0

    for number in numbers:
        # Check if the current number equals to max_and value
        if number == max_and:
            current_length += 1
        else:
            # If not, it breaks the current sequence.
            max_length = max(max_length, current_length)
            current_length = 0

    # Update one last time after the loop.
    max_length = max(max_length, current_length)
    return max_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array	Return 0, as there is no subarray.
Array with a single element	Return 1, as the single element is the longest subarray with the maximum bitwise AND (itself).
Array with all elements being 0	Return the length of the array because the bitwise AND of any subarray will be 0 which is the maximum possible AND value.
Array with all elements having the same value	Return the length of the array as any subarray will have the same maximum bitwise AND value.
Array with a very large number of elements (close to the maximum allowed size)	Ensure the solution uses an algorithm with acceptable time complexity (e.g., O(n)) to avoid timeouts.
Array with extremely large integer values that could cause integer overflow when calculating the bitwise AND (in some languages)	Use appropriate data types (e.g., long) or consider bitwise operations carefully to prevent overflow.
Array where no subarray has a bitwise AND greater than 0	The solution should correctly identify the elements with maximum value (which is 0 in this case) and return the length of subarray containing them.
Multiple subarrays have the same maximum length.	The algorithm should still return the correct (maximum) length, as only the length, not the subarray itself, is required.