2401. Longest Nice Subarray

MediumView on LeetCode

Array Bit Manipulation Sliding Window

Time: O(n)

Space: O(1)

Intuition

Longest nice subarray: no two elements share a bit. Sliding window with bitmask OR.

Algorithm

1Window [l,r]. usedBits = OR of window elements. Expand r: if (usedBits & nums[r]) != 0: shrink l (remove nums[l] from usedBits). Add nums[r].
2Track max window size.

Common Pitfalls

•Remove element from bitmask by XOR (or AND NOT). Window is valid when all elements share no bits.

2401.cs

// Approach: Sliding window with bitmask; shrink left when new element shares bits with window.
// Time: O(n) Space: O(1)

public class Solution
{
    public int LongestNiceSubarray(int[] nums)
    {
        int ans = 0;
        int used = 0;

        for (int l = 0, r = 0; r < nums.Length; ++r)
        {
            while ((used & nums[r]) > 0)
                used ^= nums[l++];
            used |= nums[r];
            ans = Math.Max(ans, r - l + 1);
        }

        return ans;
    }
}

Was this solution helpful?