Shortest Subarray With OR at Least K

Interview Problem Interview Medium Variable-size Window Array Bit Manipulation

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.minimumSubarrayLength(nums, k). nums contains nonnegative integers. Return the shortest non-empty contiguous subarray whose bitwise OR is at least k, or -1 if none exists.

Starter code

class Solution:
    def minimumSubarrayLength(self, nums, k):
        pass

Test cases

single-value

{
  "args": [
    [
      1,
      2,
      3
    ],
    2
  ]
}

Expected: 1

Wizard outline

Step 1: Initialize Solution.minimumSubarrayLength
Replace the empty starter with the first real state owned by Solution.minimumSubarrayLength. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Single Value case
Complete the readable core algorithm for one representative Interview case. Make bitwise OR removable by counting how many window values contribute each bit.
Step 4: Harden the Sum False Positive boundary
Repair the reviewed boundary and pass the complete submission contract. The bit counts reconstruct exactly the OR of the current window. For each right endpoint, shrinking while valid finds every shorter valid suffix and stops at the first invalid one, so the minimum recorded across endpoints is globally shortest.

Footguns and prerequisites

OR has no direct inverse; clearing a leaving value's bit is valid only when its contribution count becomes zero.
arrays strings two pointers sliding window
python specific rapid fire

Reviewed references

LeetCode 3097 — Shortest Subarray With OR at Least K II

Practice prerequisites

Shrink Until the Window Is Valid(opens in a new tab)
Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing shortest subarray or at least k as a complete Interview Problem.

Recommended approach and implementation

Expand right while OR-ing values and incrementing counts for their set bits. While current OR reaches k, record length and remove left by decrementing bit counts, clearing only bits whose count becomes zero.

Why it works: The bit counts reconstruct exactly the OR of the current window. For each right endpoint, shrinking while valid finds every shorter valid suffix and stops at the first invalid one, so the minimum recorded across endpoints is globally shortest.

class Solution:
    def minimumSubarrayLength(self, nums, k):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        bit_counts = [0] * 31
        current_or = 0
        left = 0
        best = len(nums) + 1
        for right, value in enumerate(nums):
            current_or |= value
            for bit in range(31):
                if value & (1 << bit):
                    bit_counts[bit] += 1
            while left <= right and current_or >= k:
                best = min(best, right - left + 1)
                outgoing = nums[left]
                for bit in range(31):
                    if outgoing & (1 << bit):
                        bit_counts[bit] -= 1
                        if bit_counts[bit] == 0:
                            current_or ^= 1 << bit
                left += 1
        return -1 if best > len(nums) else best