⚡Flashcard Drill➔
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

  1. The OR of a window only grows as the window expands, so the property is monotone and a sliding window works.
  2. Maintain the window OR together with a per-bit count, so that removing the left element can update the OR in O(1).
  3. For each right end, extend the window; while the OR is at least k, record the length and advance the left end.
  4. 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 <= right guard: without it the window can invert when k is 0.
  • Returning best unchanged when nothing qualifies: initialise best to n + 1 and 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.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems