Shortest Subarray With OR at Least K II

Shortest Subarray With OR at Least K II

What is this problem about?

The Shortest Subarray With OR at Least K II interview question extends Part I with larger input constraints (array values up to 10^9, length up to 10^5), requiring an efficient O(n log maxVal) solution. The key challenge: while a sliding window can expand easily (OR only grows), shrinking requires "undoing" OR operations — which needs tracking how many times each bit is set in the current window.

Why is this asked in interviews?

Microsoft, Meta, Amazon, and Google ask this problem because it demonstrates the sliding window pattern with a non-trivially reversible aggregate — bitwise OR. Most sliding window problems use sum (trivially reversible) or frequency (easily updated). OR requires per-bit counting to enable window shrinking. This tests advanced bit manipulation combined with sliding window design.

Algorithmic pattern used

The pattern is sliding window with per-bit count array. Maintain a bit_count[30] array tracking how many elements in the current window have each bit set. The current window OR can be computed as (1 << b) for each b where bit_count[b] > 0. When adding element nums[right]: increment bit_count[b] for each set bit. When removing element nums[left]: decrement bit_count[b] for each set bit. If bit_count[b] drops to 0, that bit is no longer set in the window's OR. While window OR ≥ K, try to shrink from the left, tracking the minimum window length.

Example explanation

Array: [1, 2, 32, 21], K = 35.

• Window [32,21]: bit_count reflects 32=100000, 21=010101. OR = 110101 = 53 ≥ 35. Length=2.
• Try shrinking: remove 32 → OR=21 < 35. Can't shrink further.

Can any window of length 1 achieve OR ≥ 35? 32<35, 21<35, 2<35, 1<35. No.

Minimum length: 2.

Common mistakes candidates make

• Using plain OR accumulation without bit counting — makes window shrinking impossible since OR can't be "undone."
• Not iterating over all 30 (or 32) bits when adding/removing elements — must update per-bit counts for all set bits.
• Off-by-one in bit range — use bits 0 through 29 for values up to 10^9.
• Recomputing the window OR from scratch each step instead of using the bit_count array — O(30) per step is fine; O(n) per step TLEs.

Interview preparation tip

For the Shortest Subarray With OR at Least K II coding problem, the sliding window bit manipulation array interview pattern with per-bit counts is the O(30n) solution. The critical insight: since OR is not directly reversible, use bit counts as a proxy — bit_count[b] > 0 iff bit b is set in the current window OR. Meta and Google interviewers ask about this technique because it generalizes: any bitwise aggregate can be made "reversible" using per-bit counts. Practice this pattern — it also solves "minimum window with AND at most K" and similar bitwise window problems.