Longest Nice Subarray

MEDIUM

Description

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⁹

Approaches

Checkout 2 different approaches to solve Longest Nice Subarray. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

Initialize maxLength = 0.
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.
Inside this loop, initialize a variable currentOr = 0 to store the bitwise OR of elements in the subarray starting at i.
Start a nested loop with an index j from i to n-1. This j will be the ending index.
For each element nums[j], check if it has any set bits in common with currentOr by evaluating (currentOr & nums[j]).
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.
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).
After both loops complete, maxLength will hold the length of the longest nice subarray found.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store state (`maxLength`, `currentOr`, loop indices), regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Longest Nice Subarray. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Longest Nice Subarray

Patterns:

Sliding WindowBit Manipulation

Data Structures:

Array

Companies:

Paytm |