NeetCode #870LC-3097MediumBit Manipulation
← Back to All Problems#870 · #3097 · Shortest Subarray With OR at Least K II(或值至少为 K 的最短子数组 II)
📌 Problem Statement & Constraints
Given an array
nums of non-negative integers and an integer k, return the length of the shortest non-empty subarray whose bitwise OR is at least k, or -1 if no such subarray exists. Constraints: 1 <= nums.length <= 2 * 10^5, 0 <= nums[i] <= 10^9, 0 <= k <= 10^9.💡 Core Algorithmic Approaches
- The OR of a window only grows as the window expands, so the property is monotone and a sliding window works.
- Maintain the window OR together with a per-bit count, so that removing the left element can update the OR in O(1).
- For each right end, extend the window; while the OR is at least
k, record the length and advance the left end. - When a bit's count drops to zero, clear that bit from the running OR.
💻 Benchmark Python3 Implementation
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
n = len(nums)
bits = [0] * 32 # how many window elements set each bit
cur = 0
left = 0
best = n + 1
for right in range(n):
x = nums[right]
cur |= x
for b in range(32):
if x >> b & 1:
bits[b] += 1
while cur >= k and left <= right:
best = min(best, right - left + 1)
y = nums[left]
for b in range(32):
if y >> b & 1:
bits[b] -= 1
if bits[b] == 0:
cur &= ~(1 << b) # the last copy of this bit left
left += 1
return best if best <= n else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(32 * n) = O(n): each index enters and leaves the window once, with 32 bits touched per move.
💾 Space Complexity
O(1): a fixed 32-entry counter array.
⚠️ Interview Pitfalls & Follow-ups
- Recomputing the window OR from scratch on every shrink: O(n * window) and too slow; the per-bit counts keep removal at O(32).
- Clearing a bit on every removal: only clear it when its count reaches zero, otherwise the OR stays inflated.
- Forgetting the
left <= rightguard: without it the window can invert whenkis 0. - Returning
bestunchanged when nothing qualifies: initialisebestton + 1and translate it to -1 at the end.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.