CODEWITHSUNDEEP
python-3.xalgorithmdata-structuresbitwise-and
Abhinav Tahlani
Abhinav Tahlani

Reputation: 199

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.)

Upvotes: 2

Views: 118

Answers (2)

Unmitigated
Unmitigated

Reputation: 89139

As an alternative, you can use itertools.groupby to get all consecutive runs of the same value.

def longestSubarray(self, nums: list[int]) -> int:
    from itertools import groupby
    mx = max(nums)
    return max(sum(1 for _ in g) for k, g in groupby(nums) if k == mx)

Upvotes: 2

tuk
tuk

Reputation: 6842

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

Upvotes: 4

Related Questions