# Longest Subarray With Maximum Bitwise AND
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-subarray-with-maximum-bitwise-and)
Canonical: https://scaleengineer.com/dsa/problems/longest-subarray-with-maximum-bitwise-and
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [fourkites](https://scaleengineer.com/companies/fourkites)
---
## Problem
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 <= 105`
* `1 <= nums[i] <= 106`

# Approaches
## Brute Force Approach
This approach directly translates the problem statement into code without leveraging any special properties of the bitwise AND operation. It systematically considers every possible contiguous subarray, calculates its bitwise AND, and keeps track of the maximum AND value seen so far (`maxAndVal`) and the length of the longest subarray that results in that value (`maxLength`).
**Time:** O(n^2), where n is the length of the input array `nums`. The nested loops result in a quadratic number of operations as we check every possible subarray. · **Space:** O(1) extra space, as we only use a few variables to store the maximum AND value, max length, and current AND value.
**Pros:** It is a straightforward implementation that correctly solves the problem.; It does not require any special insights and follows directly from the problem definition.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We use two nested loops to generate all possible subarrays. The outer loop, indexed by `i`, determines the start of the subarray. The inner loop, indexed by `j`, determines the end. For each starting position `i`, we initialize a variable `currentAnd`. As we extend the subarray by moving `j` to the right, we update `currentAnd` by performing a bitwise AND with the new element `nums[j]`. This is more efficient than recalculating the AND from scratch for every subarray. At each step, we compare the `currentAnd` of the subarray `nums[i...j]` with our global `maxAndVal`. If we find a strictly greater AND value, we update `maxAndVal` and reset `maxLength`. If we find an equal AND value, we only update `maxLength` if the current subarray is longer.

```java
class Solution {
    public int longestSubarray(int[] nums) {
        int maxAndVal = 0;
        int maxLength = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            int currentAnd = nums[i];
            // Check subarray nums[i...i]
            if (currentAnd > maxAndVal) {
                maxAndVal = currentAnd;
                maxLength = 1;
            } else if (currentAnd == maxAndVal) {
                maxLength = Math.max(maxLength, 1);
            }
            
            for (int j = i + 1; j < n; j++) {
                currentAnd &= nums[j];
                // Check subarray nums[i...j]
                if (currentAnd > maxAndVal) {
                    maxAndVal = currentAnd;
                    maxLength = j - i + 1;
                } else if (currentAnd == maxAndVal) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
1. Initialize `maxAndVal = 0` and `maxLength = 0`.
2. Iterate through the array with an outer loop index `i` from `0` to `n-1` to select a starting element for the subarray.
3. Inside the outer loop, initialize `currentAnd` with the value of `nums[i]`.
4. Start an inner loop with index `j` from `i` to `n-1` to extend the subarray to the right.
5. In each step of the inner loop, `currentAnd` represents the bitwise AND of the subarray `nums[i...j]`.
6. Compare `currentAnd` with `maxAndVal`:
   - If `currentAnd > maxAndVal`, we have found a new maximum AND value. Update `maxAndVal` to `currentAnd` and set `maxLength` to the current subarray's length (`j - i + 1`).
   - If `currentAnd == maxAndVal`, we have found another subarray with the same maximum AND. Update `maxLength` to be the maximum of its current value and the new subarray's length.
7. After both loops complete, `maxLength` will hold the length of the longest subarray that has the maximum possible bitwise AND value.

## Single-Pass Optimal Solution
This optimal approach is based on a crucial property of the bitwise AND operation: for any two numbers `a` and `b`, `a & b <= min(a, b)`. This property extends to any number of elements. Consequently, the bitwise AND of any subarray is always less than or equal to the smallest element in that subarray. This implies that the maximum possible bitwise AND of any subarray cannot exceed the maximum element in the entire array.

The maximum value is achievable by a subarray of length 1 containing just the maximum element. Therefore, the problem simplifies to finding the maximum element in the array and then finding the length of the longest contiguous subarray where all elements are equal to this maximum value.
**Time:** O(n), where n is the length of the input array `nums`. We iterate through the array only once. · **Space:** O(1) extra space. We only use a constant number of variables to track the state.
**Pros:** Extremely efficient, with optimal time and space complexity.; Solves the problem in a single pass over the input array.
**Cons:** The logic relies on a key insight about the bitwise AND operation, which may not be immediately obvious.
### Explanation
We can find the solution in a single pass through the array. We maintain three variables: `maxVal` (the maximum element encountered so far), `maxLength` (the length of the longest run of `maxVal` found so far), and `currentLength` (the length of the current contiguous run of `maxVal`).

As we iterate through the array, if we encounter a number larger than `maxVal`, we have a new maximum. We update `maxVal` and reset our length counters (`maxLength` and `currentLength`) to 1. If we encounter a number equal to `maxVal`, we are extending the current run, so we increment `currentLength` and update `maxLength` if this new run is the longest yet. If we see a number smaller than `maxVal`, it breaks any potential run of `maxVal`, so we reset `currentLength` to 0. This single pass efficiently finds both the maximum element and the longest run of it simultaneously.

```java
class Solution {
    public int longestSubarray(int[] nums) {
        int maxVal = 0;
        int maxLength = 0;
        int currentLength = 0;

        for (int num : nums) {
            if (num > maxVal) {
                // Found a new maximum value
                maxVal = num;
                maxLength = 1;
                currentLength = 1;
            } else if (num == maxVal) {
                // Continuing a run of the maximum value
                currentLength++;
                maxLength = Math.max(maxLength, currentLength);
            } else { // num < maxVal
                // The run of the maximum value is broken
                currentLength = 0;
            }
        }
        return maxLength;
    }
}
```
### Algorithm
1. Initialize `maxVal = 0` (to store the maximum element found), `maxLength = 0` (the final answer), and `currentLength = 0` (to track the length of the current run of `maxVal`).
2. Iterate through each number `num` in the input array `nums`.
3. For each `num`:
   - If `num > maxVal`: We've found a new maximum element. This new element forms a new subarray with the highest possible AND value so far. Update `maxVal = num`, and reset both `maxLength` and `currentLength` to `1`.
   - If `num == maxVal`: The current run of the maximum element continues. Increment `currentLength` and update `maxLength = max(maxLength, currentLength)`.
   - If `num < maxVal`: The current run of the maximum element is broken. Reset `currentLength = 0`.
4. After iterating through the entire array, return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestSubarray(int[] nums) {
    int mx = 0;
    for (int v : nums) {
      mx = Math.max(mx, v);
    }
    int ans = 0, cnt = 0;
    for (int v : nums) {
      if (v == mx) {
        ++cnt;
        ans = Math.max(ans, cnt);
      } else {
        cnt = 0;
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
function longestSubarray ( nums ) { const mx = Math . max (... nums ); let [ ans , cnt ] = [ 0 , 0 ]; for ( const x of nums ) { if ( x === mx ) { cnt ++ ; ans = Math . max ( ans , cnt ); } else { cnt = 0 ; } } return ans ; }
```

### CPP

```cpp
class Solution {
public:
  int longestSubarray(vector<int> &nums) {
    int mx = *max_element(nums.begin(), nums.end());
    int ans = 0, cnt = 0;
    for (int v : nums) {
      if (v == mx) {
        ++cnt;
        ans = max(ans, cnt);
      } else {
        cnt = 0;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestSubarray(self, nums: List[int]) -> int: mx = max(nums) ans = cnt = 0 for v in nums: if v == mx: cnt += 1 ans = max(ans, cnt) else: cnt = 0 return ans

```