LC-2411 Medium LeetCode

2411. Smallest Subarrays With Maximum Bitwise OR

Array Binary Search Bit Manipulation Sliding Window

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 45% Topics: Array, Binary Search, Bit Manipulation, Sliding Window

Reading material

Arrays & Hashing 12 min Binary Search 12 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

# bitmasks, hash table
class Solution(object):
    def smallestSubarrays(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = [0]*len(nums)
        lookup = [-1]*max(max(nums).bit_length(), 1)
        for i in reversed(xrange(len(nums))):
            for bit in xrange(len(lookup)):
                if nums[i]&(1<<bit):
                    lookup[bit] = i
            result[i] = max(max(lookup)-i+1, 1)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT