# Longest Nice Subarray
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-nice-subarray)
Canonical: https://scaleengineer.com/dsa/problems/longest-nice-subarray
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Paytm](https://scaleengineer.com/companies/paytm)
---
## Problem
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 <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force Iteration
This approach involves checking every possible contiguous subarray to see if it is 'nice'. For each subarray, we verify if the bitwise AND of every pair of distinct elements is zero. This is done by iterating through all possible start and end points of a subarray.
**Time:** O(n^2), where n is the number of elements in the input array. The nested loops iterate through all subarrays, leading to a quadratic runtime. · **Space:** O(1), as we only use a few variables to store state (`maxLength`, `currentOr`, loop indices), regardless of the input size.
**Pros:** Simple to understand and implement.; It is a straightforward translation of the problem definition.
**Cons:** The time complexity of O(n^2) is inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the problem constraints.
### Explanation
We use two nested loops to generate all subarrays. The outer loop, with index `i`, fixes the starting point of the subarray. The inner loop, with index `j`, extends the subarray to the right.

For each subarray starting at `i`, we maintain a variable `currentOr` which stores the bitwise OR of all elements from `nums[i]` to `nums[j-1]`. When considering the next element `nums[j]`, we check if `(currentOr & nums[j]) != 0`. If this condition is true, it means `nums[j]` shares at least one set bit with one of the previous elements in the subarray `nums[i...j-1]`. This violates the 'nice' property. At this point, we know that no subarray starting at `i` and ending at or after `j` can be nice, so we break the inner loop and proceed to the next starting position `i+1`.

If the condition is false, the subarray `nums[i...j]` is nice. We update `currentOr` to include `nums[j]`'s bits and update our `maxLength` with the new subarray's length.

```java
class Solution {
    public int longestNiceSubarray(int[] nums) {
        int n = nums.length;
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            int currentOr = 0;
            for (int j = i; j < n; j++) {
                if ((currentOr & nums[j]) != 0) {
                    break;
                }
                currentOr |= nums[j];
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
1. Initialize `maxLength = 0`.
2. Iterate through the array with an index `i` from `0` to `n-1`. This `i` will be the starting index of a potential nice subarray.
3. Inside this loop, initialize a variable `currentOr = 0` to store the bitwise OR of elements in the subarray starting at `i`.
4. Start a nested loop with an index `j` from `i` to `n-1`. This `j` will be the ending index.
5. For each element `nums[j]`, check if it has any set bits in common with `currentOr` by evaluating `(currentOr & nums[j])`.
6. If the result is not zero, it means there is a bitwise conflict. The subarray `nums[i...j]` is not nice. Since any longer subarray starting at `i` will also include this conflict, we can break the inner loop.
7. If there is no conflict, the subarray `nums[i...j]` is nice. We update `currentOr` by including the bits of `nums[j]` (`currentOr |= nums[j]`) and update `maxLength = Math.max(maxLength, j - i + 1)`.
8. After both loops complete, `maxLength` will hold the length of the longest nice subarray found.

## Sliding Window
A more efficient approach uses the sliding window technique. We maintain a 'window' (a subarray) that is always nice. We try to expand this window by moving its right boundary. If adding a new element violates the 'nice' property, we shrink the window from the left until it becomes nice again.
**Time:** O(n), where n is the number of elements. Both the `right` and `left` pointers traverse the array at most once in total, leading to an amortized O(1) time for each step of the `right` pointer. · **Space:** O(1), as we only use a constant amount of extra space for variables like `left`, `maxLength`, and `currentOr`.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Optimal space complexity, using only a constant amount of extra memory.
**Cons:** The logic, especially the shrinking part with the XOR operation, can be slightly less intuitive to come up with compared to the brute-force method.
### Explanation
The core idea is to maintain a window `[left, right]` that represents a nice subarray. We use a variable `currentOr` to store the bitwise OR of all elements within this window. The 'nice' property means that for any two numbers in the window, their bitwise AND is 0. This is equivalent to saying that for any new element `nums[right]` we want to add, it must not share any set bits with the combined bits of the current window.

We iterate through the array with the `right` pointer. For each `nums[right]`, we check for a conflict with the OR of the elements currently in the window `[left, right-1]`.
- If there's a conflict (`(currentOr & nums[right]) != 0`), we must shrink the window from the left. We do this by incrementing `left` and removing `nums[left]`'s contribution from `currentOr`. Since all numbers in a nice window are bit-disjoint, we can simply use the XOR operation: `currentOr ^= nums[left]`. We repeat this until the conflict is resolved.
- Once the conflict is resolved (or if there was none), we can safely expand the window. We add `nums[right]` to the window by updating `currentOr |= nums[right]`. 
- At each step, the window `[left, right]` is nice, so we update our `maxLength` with its current size `right - left + 1`.

```java
class Solution {
    public int longestNiceSubarray(int[] nums) {
        int left = 0;
        int maxLength = 0;
        int currentOr = 0;
        for (int right = 0; right < nums.length; right++) {
            // While the new number has bits in common with the current window's OR value
            while ((currentOr & nums[right]) != 0) {
                // Shrink the window from the left
                // Remove the leftmost element's bits from the OR value
                currentOr ^= nums[left];
                left++;
            }
            // Expand the window to the right
            // Add the new number's bits to the OR value
            currentOr |= nums[right];
            // Update the maximum length found so far
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```
### Algorithm
1. Initialize `left = 0`, `maxLength = 0`, and `currentOr = 0`.
2. Iterate through the array with a `right` pointer from `0` to `n-1`.
3. Inside the loop, check if the new element `nums[right]` conflicts with the current window's combined bits `currentOr`.
4. Use a `while` loop: `while ((currentOr & nums[right]) != 0)` to handle conflicts:
   a. Shrink the window from the left by removing `nums[left]`'s bits from `currentOr`: `currentOr ^= nums[left]`.
   b. Move the left boundary: `left++`.
5. After the `while` loop, the conflict is resolved. Expand the window by including `nums[right]`: `currentOr |= nums[right]`.
6. The window `[left, right]` is now the longest nice subarray ending at `right`. Update the result: `maxLength = Math.max(maxLength, right - left + 1)`.
7. After the main loop finishes, return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestNiceSubarray(int[] nums) {
    int ans = 0, mask = 0;
    for (int i = 0, j = 0; i < nums.length; ++i) {
      while ((mask & nums[i]) != 0) {
        mask ^= nums[j++];
      }
      ans = Math.max(ans, i - j + 1);
      mask |= nums[i];
    }
    return ans;
  }
}

```

### CSharp

```csharp
public class Solution {
    public int LongestNiceSubarray(int[] nums) {
        int ans = 0, mask = 0;
        for (int i = 0, j = 0; i < nums.Length; ++i) {
            while ((mask & nums[i]) != 0) {
                mask ^= nums[j++];
            }
            ans = Math.Max(ans, i - j + 1);
            mask |= nums[i];
        }
        return ans;
    }
}
```

### CPP

```cpp
class Solution {
public:
  int longestNiceSubarray(vector<int> &nums) {
    int ans = 0, mask = 0;
    for (int i = 0, j = 0; i < nums.size(); ++i) {
      while (mask & nums[i]) {
        mask ^= nums[j++];
      }
      ans = max(ans, i - j + 1);
      mask |= nums[i];
    }
    return ans;
  }
};

```

### Python

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

```