Longest Subarray with Maximum Bitwise And

LeetCode 2419

You’ve likely read the question and are here to find a solution or, more specifically, to discover the optimal solution.

Before diving into solving the problem, let’s start by understanding the core concept that drives this challenge of this question bitwise AND. If you’re new to bitwise operations, think of it as a way to compare the binary representations of two numbers.

Here’s how bitwise AND works:

• If both bits in a given position are 1, the result is 1.
• If either or both bits are 0, the result is 0.

Like : **- 5 in binary: 101

• 3 in binary: 011**

When you apply bitwise AND (&) to them:

101 & 011 — — - 001 (which equals 1)

NOTE : This concept can extend beyond two numbers. You can AND several numbers together, and the result will keep shrinking unless all bits in the corresponding positions are 1.

The Power of Subarrays

A subarray is simply a contiguous part of an array. For example, if you have an array nums = [1, 2, 3], then the subarrays would be: [1], [2], [3], [1, 2], [2, 3], [1, 2, 3]

Problem Statement:

Subarrays are at the core of this problem because we’re asked to find the longest subarray where the bitwise AND of all its elements is maximized. The challenge is to determine which subarrays we should focus on and how to efficiently find the longest one.

We are given an array nums, and our task is to:

1. Identify the maximum bitwise AND that any subarray can have.
2. Find the longest subarray where the bitwise AND equals this maximum value.

Building Intuition

1. Maximum AND Value of Any Subarray

First, we need to figure out what the maximum bitwise AND can be in the array. Here’s the trick: the maximum AND value will always come from the largest element in the array. Why? Because bitwise AND reduces values, meaning if you start with a smaller number, the result will always be smaller or equal to it.

So, to get the largest AND possible, you have to include the largest number in that subarray.

2. Focus on Subarrays Containing the Maximum Element

Once we know the largest number in nums, the next task is to find the longest subarray where the AND operation continues to give this maximum value. If you include other numbers that aren’t the maximum, the AND result will decrease.

Thus, the challenge boils down to finding the longest contiguous segment in the array where all elements are equal to this maximum value.

3. Efficient Solution

Here’s the plan: We find the maximum value in the array. We then traverse the array and find the longest contiguous subarray where each element equals this maximum value.

We can solve this in a single pass over the array, keeping track of the longest sequence of elements that match the maximum value.

def longest_subarray(nums):
    max_num = max(nums)  # Step 1: Find the maximum value
    longest = 0
    current_length = 0

    # Step 2: Traverse the array and find the longest subarray with max_num
    for num in nums:
        if num == max_num:
            current_length += 1  # Keep extending the current subarray
        else:
            longest = max(longest, current_length)  # Update the longest subarray length
            current_length = 0  # Reset the count if we encounter a different number

    # After the loop, we need to update longest for the last sequence
    longest = max(longest, current_length)

    return longest

1. We first find the maximum value in nums. This will be the target value for the bitwise AND.
2. As we loop through the array, we track how long we can keep finding contiguous elements equal to max_num. Each time we hit an element that’s not equal to max_num, we check if the current streak of contiguous elements is the longest so far.
3. Edge Case: If the entire array consists of just one element (or all elements are the same), the result is straightforward: the length of the array.
4. This problem might seem tricky at first because of the mention of bitwise AND, but breaking it down reveals that we’re really just looking for subarrays filled with the largest number. Once you identify that, finding the longest such subarray becomes a simple problem of tracking sequences.
5. The key takeaway is that understanding bitwise operations helps us recognize how they affect values in an array, and from there, we can efficiently focus on the part of the array that really matters.