Shortest Subarray With OR at Least K II Solution in Python

Problem Description

Ah, the classic “Shortest Subarray With OR at Least K II” problem! It’s like trying to find the shortest line at the DMV, but instead, you’re sifting through an array of numbers to find the smallest subarray whose bitwise OR is at least K. Imagine you’re at a buffet, and you want to fill your plate with the least amount of food while still getting enough to satisfy your hunger. But instead of food, you have numbers, and instead of hunger, you have a requirement for a bitwise OR.

In simpler terms, given an array of integers, you need to find the length of the shortest contiguous subarray such that the bitwise OR of all the elements in that subarray is at least K. If no such subarray exists, you return -1.

Code Solution


class Solution:
    def minimumSubarrayLength(self, nums: list[int], k: int) -> int:
        ans = len(nums) + 1
        ors = 0
        count = collections.Counter()

        l = 0
        for r, num in enumerate(nums):
            ors = self._orNum(ors, num, count)
            while ors >= k and l <= r:
                ans = min(ans, r - l + 1)
                ors = self._undoOrNum(ors, nums[l], count)
                l += 1

        return -1 if ans == len(nums) + 1 else ans

    def _orNum(self, ors: int, num: int, count: dict[int, int]) -> int:
        for i in range(30):
            if num >> i & 1:
                count[i] += 1
                if count[i] == 1:
                    ors += 1 << i
        return ors

    def _undoOrNum(self, ors: int, num: int, count: dict[int, int]) -> int:
        for i in range(30):
            if num >> i & 1:
                count[i] -= 1
                if count[i] == 0:
                    ors -= 1 << i
        return ors

Approach Explanation

The approach taken in this solution is a sliding window technique combined with bitwise operations. The idea is to maintain a window defined by two pointers (l and r) and calculate the bitwise OR of the elements within this window.

Initialization: Start with an answer set to a value larger than any possible subarray length and initialize the OR value and a counter for the bits.
Expand the Window: Iterate through the array with the right pointer (r), updating the OR value and the bit count.
Contract the Window: Whenever the OR value meets or exceeds K, attempt to shrink the window from the left (l) to find the minimum length that still satisfies the condition.
Return Result: If a valid subarray is found, return its length; otherwise, return -1.

Time and Space Complexity

Time Complexity: O(N * 30) = O(N), where N is the number of elements in the array. The factor of 30 comes from the bitwise operations, as we are only considering the first 30 bits of the integers.

Space Complexity: O(1) for the OR value and O(30) for the bit count, which is effectively O(1) since it’s a constant size.

Real-World Example

Imagine you’re at a party, and you want to gather the shortest group of friends who can collectively tell the best jokes (the jokes being the numbers in the array). You want to ensure that the combined humor (bitwise OR) of this group is at least a certain level (K). You start gathering friends one by one, and as soon as you hit that humor threshold, you check if you can drop some friends from the front of the line while still keeping the humor level up.