python-3.xalgorithmdata-structuresbitwise-and

Longest Subarray with Maximum Bitwise AND


This is based on a problem from LeetCode (#2419) Longest Subarray with Maximum Bitwise AND

I'm not concerned with the logic related to the problem (I need to find the longest chain of maximum elements (max of array)). Here's my solution -

    max_index = nums.index(max(nums))
    max_val = max(nums)
    ans, temp = 1, 1
    for i in range(max_index+1, len(nums)):
        if (nums[i]==max_val):
            temp+=1
        else:
            ans = max(ans, temp)
            temp=1
    ans = max(ans, temp)
    return ans

This fetches me a wrong answer in one of the test cases where the length of the array is fairly large - enter image description here

The expected answer is 125, whereas my code fetches me an answer of 126. What can be the problem with my code that causes it to fail for a large test case? I felt I had accounted for all the edge cases possible (chain of max elements at the end of the array, equal length chains, etc.)


Solution

  • Updating the code in the question

    def longestSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_index = nums.index(max(nums))
        max_val = max(nums)
        ans, temp = 1, 1
        for i in range(max_index+1, len(nums)):
            if (nums[i]==max_val):
                temp+=1
                ans = max(ans, temp)
            else:
                temp=0
        return ans
    

    Approach

    1. Find the maximum value in the array
    2. Traverse the array, counting the consecutive element equal to the maximum value found in #1

    It can be simplified if it can be done like

    def longestSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_val = max(nums)
        ans, temp = 0, 0
        for num in nums:
            if (num==max_val):
                temp+=1
                ans = max(ans, temp)
            else:
                temp=0
        return ans