Longest Nice Subarray

Med

#2185Time: 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.1 company

Patterns

Sliding Window Bit Manipulation

Data structures

Array

Companies

Paytm

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1class Solution {2    public int longestNiceSubarray(int[] nums) {3        int n = nums.length;4        int maxLength = 0;5        for (int i = 0; i < n; i++) {6            int currentOr = 0;7            for (int j = i; j < n; j++) {8                if ((currentOr & nums[j]) != 0) {9                    break;10                }11                currentOr |= nums[j];12                maxLength = Math.max(maxLength, j - i + 1);13            }14        }15        return maxLength;16    }17}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Initialize left = 0, maxLength = 0, and currentOr = 0.
Iterate through the array with a right pointer from 0 to n-1.
Inside the loop, check if the new element nums[right] conflicts with the current window's combined bits currentOr.
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++.
After the while loop, the conflict is resolved. Expand the window by including nums[right]: currentOr |= nums[right].
The window [left, right] is now the longest nice subarray ending at right. Update the result: maxLength = Math.max(maxLength, right - left + 1).
After the main loop finishes, return maxLength.

Walkthrough

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.

1class Solution {2    public int longestNiceSubarray(int[] nums) {3        int left = 0;4        int maxLength = 0;5        int currentOr = 0;6        for (int right = 0; right < nums.length; right++) {7            // While the new number has bits in common with the current window's OR value8            while ((currentOr & nums[right]) != 0) {9                // Shrink the window from the left10                // Remove the leftmost element's bits from the OR value11                currentOr ^= nums[left];12                left++;13            }14            // Expand the window to the right15            // Add the new number's bits to the OR value16            currentOr |= nums[right];17            // Update the maximum length found so far18            maxLength = Math.max(maxLength, right - left + 1);19        }20        return maxLength;21    }22}

Complexity

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`.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int longestNiceSubarray(int[] nums) {4    int ans = 0, mask = 0;5    for (int i = 0, j = 0; i < nums.length; ++i) {6      while ((mask & nums[i]) != 0) {7        mask ^= nums[j++];8      }9      ans = Math.max(ans, i - j + 1);10      mask |= nums[i];11    }12    return ans;13  }14}

1public class Solution {2    public int LongestNiceSubarray(int[] nums) {3        int ans = 0, mask = 0;4        for (int i = 0, j = 0; i < nums.Length; ++i) {5            while ((mask & nums[i]) != 0) {6                mask ^= nums[j++];7            }8            ans = Math.Max(ans, i - j + 1);9            mask |= nums[i];10        }11        return ans;12    }13}

1class Solution {2public:3  int longestNiceSubarray(vector<int> &nums) {4    int ans = 0, mask = 0;5    for (int i = 0, j = 0; i < nums.size(); ++i) {6      while (mask & nums[i]) {7        mask ^= nums[j++];8      }9      ans = max(ans, i - j + 1);10      mask |= nums[i];11    }12    return ans;13  }14};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem