2419. Longest Subarray With Maximum Bitwise AND

Time: O(n)

Space: O(1)

Intuition

Find the longest subarray where bitwise AND of all elements is greater than 0. AND can only decrease as we add elements. All elements must share at least one common bit.

Algorithm

1Sliding window: AND of window > 0. When AND becomes 0: move left pointer.
2Or: for each bit, find max run where that bit is set in all elements.

Common Pitfalls

•AND of subarray is > 0 iff some bit is set in all elements. Max such contiguous run.

2419.cs

// Approach: Find global max; find longest run of consecutive equal-to-max elements.
// Time: O(n) Space: O(1)

public class Solution
{
    public int LongestSubarray(int[] nums)
    {
        int ans = 0;
        int maxIndex = 0;
        int sameNumLength = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == nums[maxIndex])
                ans = Math.Max(ans, ++sameNumLength);
            else if (nums[i] > nums[maxIndex])
            {
                maxIndex = i;
                sameNumLength = 1;
                ans = 1;
            }
            else
                sameNumLength = 0;
        }

        return ans;
    }
}

Was this solution helpful?