1. Shortest Subarray With OR at Least K I (LeetCode)
Model answer
The task
Find the length of the shortest non-empty contiguous subarray whose bitwise OR is at least k. Return -1 if no such subarray exists.
Key idea
A sliding window works because adding elements can only add set bits to its OR, but removing an element may clear a bit only if no other window element has it. Track how many times each bit appears so the window OR can be updated correctly as its left edge moves.
Approach
- Keep a count for each bit position and the OR of the current window.
- Expand the window one element at a time, adding its set bits to the counts.
- While the window OR is at least
k, record its length and remove its leftmost element. - When a bit’s count drops to zero, clear that bit from the window OR.
- Return the shortest length found, or
-1if none was found.
from typing import List
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
if not nums:
return -1
bit_count = [0] * max(1, max(nums).bit_length())
window_or = 0
left = 0
shortest = len(nums) + 1
for right, value in enumerate(nums):
# Add this value's set bits to the window.
for bit in range(len(bit_count)):
mask = 1 << bit
if value & mask:
bit_count[bit] += 1
window_or |= mask
# Shrink while the current window satisfies the target.
while left <= right and window_or >= k:
shortest = min(shortest, right - left + 1)
outgoing = nums[left]
for bit in range(len(bit_count)):
mask = 1 << bit
if outgoing & mask:
bit_count[bit] -= 1
if bit_count[bit] == 0:
window_or &= ~mask
left += 1
return shortest if shortest <= len(nums) else -1
Complexity:
- Time: O(nB), where
Bis the number of bit positions needed for the input values. - Space: O(B) for the per-bit counts.
Common follow-ups
- What if the condition were OR equal to
k? Track qualifying windows carefully; “at least” no longer gives the same shrink condition. - Can bit updates be made faster? Iterate only over set bits of each value rather than over all
Bpositions. - What if the operation were bitwise AND? Maintain per-bit counts and consider how bits change as the window expands and shrinks.