LC-3097 Medium LeetCode

3097. Shortest Subarray With OR at Least K II

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 50% Topics: Array, Bit Manipulation, Sliding Window

Reading material

Arrays & Hashing 12 min Bit Manipulation 10 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(nlogr) = O(n * 30)
# Space: O(logr) = O(30)

# freq table, two pointers
class Solution(object):
    def minimumSubarrayLength(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def update(x, d, curr):
            for i in xrange(len(cnt)):
                if x < (1<<i):
                    break
                if not (x&(1<<i)):
                    continue
                if cnt[i] == 0:
                    curr ^= 1<<i
                cnt[i] += d
                if cnt[i] == 0:
                    curr ^= 1<<i
            return curr

        total = reduce(lambda x, y: x|y, nums)
        if total < k:
            return -1
        cnt = [0]*total.bit_length()
        result = len(nums)
        left = curr = 0
        for right in xrange(len(nums)):
            curr = update(nums[right], +1, curr)
            while left <= right and curr >= k:
                result = min(result, right-left+1)
                curr = update(nums[left], -1, curr)
                left += 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT