Problem Statement
Brute Force [TLE]
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
N = len(nums)
res = float('inf')
for i in range(N):
curr = nums[i]
for j in range(i, N):
curr = curr | nums[j]
if curr >= k:
res = min(res, j - i + 1)
break
return res if res != float('inf') else -1
Editorial
Approach 1: Binary Search
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
# Binary search on the length of subarray
left, right = 1, len(nums)
min_length = -1
while left <= right:
mid = left + (right - left) // 2
if self._has_valid_subarray(nums, k, mid):
min_length = mid
right = mid - 1 # Try to find smaller length
else:
left = mid + 1 # Try larger length
return min_length
def _has_valid_subarray(
self, nums: list, target_sum: int, window_size: int
) -> bool:
# Tracks count of set bits at each position
bit_counts = [0] * 32
# Sliding window approach
for right in range(len(nums)):
# Add current number to window
self._update_bit_counts(bit_counts, nums[right], 1)
# Remove leftmost number if window exceeds size
if right >= window_size:
self._update_bit_counts(
bit_counts, nums[right - window_size], -1
)
# Check if current window is valid
if (
right >= window_size - 1
and self._convert_bits_to_num(bit_counts) >= target_sum
):
return True
return False
def _update_bit_counts(
self, bit_counts: list, number: int, delta: int
) -> None:
# Update counts for each set bit in the number
for pos in range(32):
if number & (1 << pos):
bit_counts[pos] += delta
def _convert_bits_to_num(self, bit_counts: list) -> int:
# Convert bit counts to number using OR operation
return sum(1 << pos for pos in range(32) if bit_counts[pos])
Approach 2: Sliding Window
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
min_length = float("inf")
window_start = window_end = 0
bit_counts = [0] * 32 # Tracks count of set bits at each position
# Expand window until end of array
while window_end < len(nums):
# Add current number to window
self._update_bit_counts(bit_counts, nums[window_end], 1)
# Contract window while OR value is valid
while (
window_start <= window_end
and self._convert_bits_to_num(bit_counts) >= k
):
# Update minimum length found so far
min_length = min(min_length, window_end - window_start + 1)
# Remove leftmost number and shrink window
self._update_bit_counts(bit_counts, nums[window_start], -1)
window_start += 1
window_end += 1
return -1 if min_length == float("inf") else min_length
def _update_bit_counts(
self, bit_counts: list, number: int, delta: int
) -> None:
# Update counts for each set bit in the number
for pos in range(32):
if number & (1 << pos):
bit_counts[pos] += delta
def _convert_bits_to_num(self, bit_counts: list) -> int:
# Convert bit counts to number using OR operation
result = 0
for pos in range(32):
if bit_counts[pos]:
result |= 1 << pos
return result
