[LeetCode] 2401. Longest Nice Subarray

Problem

https://leetcode.com/problems/longest-nice-subarray/description

Leetcode - Longest Nice Subarray

Type - Sliding window, Two pointers, Bitmask

Difficulty - Medium

Approach & Solution

If bitwise ANDs for all pairs in subarray are 0, bitwise AND of all elements in subarray must be 0.

So, managing current subarray’s occupied bit makes the problem simple.

Data Structures and Variables

• occupied: bit slot for occupation in subarray.

• left: next index to be popped from subarray.

• right: next index to be appended to subarray.

Algorithm:

1. As we iterate through the nums, we will append nums[right] into the subarray.

2. If conflict occurs, move the left pointer with popping nums[left] from occupied.

   • i.e. pop the nums[left] and slide left to left+1.

3. Append nums[right] to subarray.

4. Update ans if the length of subarray(right - left + 1) is longer.

5. After iteration, return ans, which is maximized.

Complexity

• Time Complexity: O(n)

  • Every elements in nums can be added and removed at most once.

• Space Complexity: O(1)

  • No extra data structures.

Code (C++ | Go)

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int n = nums.size();
        int occupied = 0;
        int left = 0;

        int ans = 0;
        for(int right = 0; right < n; right++) {
            while(left < right && (occupied & nums[right]) != 0) {
                occupied &= ~(nums[left]);
                left++;
            }
            occupied |= nums[right];
            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};

func longestNiceSubarray(nums []int) int {
    occupied := 0
    left := 0
    ans := 0

    for right, num := range nums {
        for left < right && (occupied & num) != 0 {
            occupied &= ^nums[left]
            left++
        }
        occupied |= num
        ans = max(ans, right - left + 1)
    }

    return ans
}