2401. Longest Nice Subarray

MediumBit ManipulationArraySliding Window
Leetcode Link

Problem Description

This LeetCode problem requires us to find the longest subarray in a given array nums of positive integers where the subarray is considered nice. A subarray is defined as nice if the bitwise AND of every pair of elements at different positions is equal to 0. A subarray is a contiguous part of the array, and it is given that any subarray with a length of 1 is always nice.

Intuition

The solution for the problem leverages the properties of bitwise AND operation. The bitwise AND of any two numbers is 0 only if they do not share any common set bits in their binary representation.

The approach taken here uses a sliding window technique to iterate over the array, using two pointers (or indices) to define the current window which is examined for being a nice subarray. As we iterate from 0 to n-1 (where n is the length of the array), we maintain a variable mask which is the bitwise OR of all numbers in the current window. This mask helps in checking if any incoming number will create a pair with a non-zero AND with any number in the current window.

When we attempt to extend the window by including the next number, we check if the bitwise AND of this new number (x) with the current mask is zero. If it is not zero, this means the number shares at least one common set bit with one of the numbers in the current window and hence cannot be included to maintain it a nice subarray. We then shrink the window from the left by removing the leftmost element and updating the mask until the mask AND the new number is 0.

The variable ans keeps track of the length of the longest nice subarray encountered so far, and we update it every time we find a larger nice subarray. The current window's length is calculated as i - j + 1, where i is the end of the current window and j is the start.

By scanning and adjusting the window this way until the end of the array is reached, we ensure that the longest nice subarray is found.

Learn more about Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How many ways can you arrange the three letters A, B and C?

Solution Approach

The reference solution uses a sliding window technique to find the length of the longest nice subarray. Here's how the implementation unfolds:

  • An integer ans is initialized to 0 to keep track of the length of the maximum nice subarray found so far.
  • Two pointers, i and j, are initialized to track the starting and ending index of the current subarray, starting from 0.
  • An integer mask is also initiated to 0. This mask will store the bitwise OR of all numbers currently in the window.

The implementation follows these steps:

  1. Enumerate through each element x in nums using its index i.
  2. While the current number x has a non-zero AND with the mask (i.e., mask & x is not 0), i.e., if the current element shares a common set bit with any element in the subarray represented by mask, it suggests that the subarray is not nice anymore with the addition of x:
    • Exclude the leftmost element from the subarray to make room for x by XOR-ing the leftmost element nums[j] with the mask. This effectively removes the bits of nums[j] from mask.
    • Increment j to shrink the subarray from the left.
  3. After ensuring that including x will not break the nice property (the AND of every pair is 0), we can:
    • Update the ans variable with the maximum of its current value and the size of the window which is i - j + 1.
    • Include x in the mask by performing a bitwise OR (mask |= x).

This process continues for every element in the array. By iteratively adjusting the window and updating the mask, the algorithm ensures it never includes a pair that would result in a non-zero AND, hence maintaining the nice property of the subarray.

After completing the iteration over all elements, the final value of ans yields the length of the longest nice subarray.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Let's walk through an example using the solution approach.

Consider the following array nums: [3,6,1,2]

  • Initialize ans to 0.
  • Start with i = 0, j = 0, and mask = 0.

Now, we'll iterate over the array while applying the steps outlined in the solution approach:

  1. For i = 0, x = nums[0] = 3.

    • mask & x is 0 since mask starts at 0 and any number AND 0 is 0.
    • Update ans to max(ans, i - j + 1), which is 1.
    • Update mask to mask | x, which now becomes 3.

  2. Move to i = 1, x = nums[1] = 6.

    • mask & x is 2 (binary 0010), which is not 0, so we need to adjust the subarray.
    • We shrink the window by removing nums[j] (3) from mask. New mask is 3 XOR 3 = 0.
    • Increment j to 1, and now the subarray is empty.
    • We retry with x = 6, mask & x is now 0, so we can proceed.
    • Update ans to max(ans, i - j + 1), which is 1.
    • Update mask to mask | x, which now becomes 6.

  3. Move to i = 2, x = nums[2] = 1.

    • mask & x is 0, it's already a nice subarray upon adding x.
    • Update ans to max(ans, i - j + 1), which is now 2 as the subarray from nums[1] to nums[2] is nice.
    • Update mask to mask | x, which becomes 7.

  4. Move to i = 3, x = nums[3] = 2.

    • mask & x is 2, which is not 0, so the subarray is not nice with the addition of x.
    • We shrink the window from the left by excluding nums[j] (6) from mask. After XOR with 6, the new mask is 1.
    • Increment j to 2, and now the subarray starts at nums[2].
    • We retry with x = 2, mask & x is now 0, so we can proceed.
    • Update ans to max(ans, i - j + 1), which remains 2.
    • Include x in the mask, new mask is 1 | 2 = 3.

After going through the array, the final value of ans is 2, indicating the length of the longest nice subarray is 2, which corresponds to the subarray [1,2].

Solution Implementation

1from typing import List
2
3class Solution:
4    def longestNiceSubarray(self, nums: List[int]) -> int:
5        # Initialize the maximum length of the subarray, the current start of the subarray, 
6        # and the mask used to track unique bits
7        max_length = start_index = bit_mask = 0
8      
9        # Enumerate over the list of numbers
10        for end_index, number in enumerate(nums):
11            # While there is a common bit set in bit_mask and the current number
12            while bit_mask & number:
13                # Remove the bits of nums[start_index] from bit_mask
14                bit_mask ^= nums[start_index]
15                # Move the start_index forward as those bits are no longer part of the subarray
16                start_index += 1
17            # Update max_length if we've found a longer subarray that's nice
18            max_length = max(max_length, end_index - start_index + 1)
19            # Include the bits of the current number in the bit_mask
20            bit_mask |= number
21          
22        # Return the length of the longest nice subarray
23        return max_length
24
1class Solution {
2    public int longestNiceSubarray(int[] nums) {
3        // Initialize the answer to track the length of the longest nice subarray
4        int longestNiceLength = 0;
5
6        // Create a bitmask to keep track of the bits in the current subarray
7        int currentMask = 0;
8
9        // Two pointers - j represents the start of the current subarray
10        // i represents the current end of the subarray being considered
11        for (int startIdx = 0, endIdx = 0; endIdx < nums.length; ++endIdx) {
12            // Keep removing numbers from the start of the subarray until
13            // the current number can fit in without sharing any common set bits
14            while ((currentMask & nums[endIdx]) != 0) {
15                // XOR operation removes the bits of nums[startIdx] from currentMask
16                currentMask ^= nums[startIdx++];
17            }
18
19            // Update the longestNiceLength if the current subarray is longer
20            longestNiceLength = Math.max(longestNiceLength, endIdx - startIdx + 1);
21
22            // Include the current number's bits into the currentMask
23            currentMask |= nums[endIdx];
24        }
25
26        // Return the length of the longest nice subarray
27        return longestNiceLength;
28    }
29}
30
1class Solution {
2public:
3    // Function to find the length of the longest nice subarray
4    int longestNiceSubarray(vector<int>& nums) {
5        int maxLength = 0; // Variable to store the maximum length found
6        int currentMask = 0; // Bitmask to store the current state of numbers in the subarray
7      
8        // Two pointers, i for the end of the current subarray, j for the start
9        for (int end = 0, start = 0; end < nums.size(); ++end) {
10            // While there is a bit overlapping (i.e., not nice subarray), remove the starting number
11            while (currentMask & nums[end]) {
12                // ^ is the bitwise XOR, which removes nums[start] from currentMask
13                currentMask ^= nums[start++];
14            }
15            // Update maxLength with the larger of the two: previous maxLength or the current subarray length
16            maxLength = max(maxLength, end - start + 1);
17            // |= is bitwise OR and equals, which adds nums[end] to currentMask
18            currentMask |= nums[end];
19        }
20        // Return the maximum length of nice subarray found
21        return maxLength;
22    }
23};
24
1function longestNiceSubarray(nums: number[]): number {
2    let currentSubarrayBitmask = 0;  // bitmask to represent the current subarray
3
4    let maxLength = 0; // this will store the length of the longest nice subarray
5    let start = 0;     // start index of the current subarray
6  
7    // Iterating through the given array of numbers
8    for (let end = 0; end < nums.length; ++end) {
9        // Continue removing numbers from the start of the current subarray
10        // until the current number and the subarray have no common set bits.
11        while ((currentSubarrayBitmask & nums[end]) !== 0) {
12            // Using XOR to remove the start number's bits from the bitmask
13            currentSubarrayBitmask ^= nums[start++];
14        }
15
16        // Update the maximum length of a nice subarray if current subarray is longer
17        maxLength = Math.max(maxLength, end - start + 1);
18      
19        // Add the current number's bits to the bitmask
20        currentSubarrayBitmask |= nums[end];
21    }
22
23    // Return the length of the longest nice subarray
24    return maxLength;
25}
26
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

Time and Space Complexity

The time complexity of the provided code is O(N), where N is the length of the nums array. This is because the code iterates over all the elements of nums exactly once with the outer loop (for i, x in enumerate(nums):). The inner while-loop (while mask & x:) only processes each element at most once across the entire runtime because once an element has been removed from the mask (mask ^= nums[j]), it does not get reprocessed. Thus, each element contributes at most two operations: one for adding it to the mask and one for possibly removing it from the mask, leading to a linear runtime overall.

The space complexity of the code is O(1) since the amount of extra space used by the algorithm does not scale with the input size N. The data structures used (ans, j, and mask) require a constant amount of space regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these properties could exist for a graph but not a tree?

Recommended Readings

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫