DDSA Solutions

2419. Longest Subarray With Maximum Bitwise AND

MediumView on LeetCode
ArrayBit Manipulation
Time: O(n)
Space: O(1)

Problem Overview

Find the longest subarray where bitwise AND of all elements is greater than 0.

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

  1. 1Sliding window: AND of window > 0. When AND becomes 0: move left pointer.
  2. 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
C#
// 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?

Related Problems