Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Sliding Window

Solution

LeetCode 3097 - Shortest Subarray With OR at Least K II

Problem Understanding

This problem asks us to find the smallest non-empty contiguous subarray whose bitwise OR is at least k.

The input consists of:

An integer array nums
An integer k

For any subarray nums[left:right+1], we compute the bitwise OR of all elements inside that range. If the resulting value is greater than or equal to k, then that subarray is considered special.

Our goal is to return the minimum possible length among all special subarrays. If no subarray satisfies the condition, we return -1.

The important detail here is that the operation is bitwise OR, not sum. OR behaves differently from arithmetic operations:

Once a bit becomes 1, it stays 1
Adding more numbers to the subarray can only keep or increase the OR value
Removing elements from the left side may reduce the OR value, but recalculating that efficiently is not trivial

The constraints are large:

nums.length can be up to 2 * 10^5
Values can be as large as 10^9

A quadratic solution that checks every subarray is far too slow. We need something close to linear time.

Several edge cases are important:

k = 0, every non-empty subarray automatically satisfies the condition because OR is always non-negative
Arrays where no subarray can ever reach k
Single-element answers
Large arrays containing many repeated values
Situations where removing one element changes multiple OR bits

Understanding how to maintain OR information efficiently while sliding a window is the key challenge.

Approaches

Brute Force

The most straightforward solution is to examine every possible subarray.

For each starting index:

Extend the subarray one element at a time
Maintain the running OR
As soon as the OR becomes at least k, update the minimum length

This approach is correct because it explicitly evaluates all possible subarrays.

However, the complexity is too large. There are O(n^2) subarrays, and although OR accumulation itself is cheap, the total work becomes unacceptable for n = 2 * 10^5.

Optimal Approach, Sliding Window with Bit Frequency Counting

The key observation is that bitwise OR is determined entirely by which bits are present in the current window.

Instead of storing the OR directly, we maintain:

A sliding window
A count of how many numbers in the window contribute each bit

For every bit position:

If the count is greater than zero, that bit exists in the window OR
If the count becomes zero, that bit disappears from the window OR

This allows us to dynamically add and remove elements while maintaining the exact OR value in O(32) time per operation.

Since integers are at most 10^9, we only need 31 bits.

The algorithm becomes:

Expand the right side of the window
Update bit counts
While the OR is at least k, shrink the left side
Track the minimum valid length

This transforms the solution into an efficient linear-time sliding window algorithm.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every subarray explicitly
Optimal	O(32 × n)	O(32)	Sliding window with bit frequency tracking

Algorithm Walkthrough

Initialize a sliding window using two pointers, left and right.

The window represents the current subarray being considered. 2. Maintain an array bit_count[32].

bit_count[b] stores how many numbers in the current window contain bit b. 3. Maintain the current OR value of the window.

Whenever a new number is added:

Check all 32 bits
If bit b is set in the number:
Increment bit_count[b]
If this count changes from 0 to 1, enable that bit in the current OR

Expand the window by moving right.

Add nums[right] into the window and update the OR information. 5. After every expansion, check whether the current OR is at least k.

If it is, then the current window is valid. 6. While the window remains valid:

Update the answer with the current window size
Remove nums[left]
Decrease the corresponding bit counts
If any bit count becomes zero, remove that bit from the OR
Move left forward

Continue until all elements have been processed.
If no valid window was found, return -1.

Why it works

The sliding window guarantees that every contiguous subarray is considered in an efficient order.

The bit frequency array correctly represents the OR value because a bit is present in the OR if and only if at least one number in the window contains that bit.

By shrinking the window greedily whenever the OR condition is satisfied, we ensure that we always find the shortest valid subarray ending at each position.

Python Solution

from typing import List

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        if k == 0:
            return 1

        bit_count = [0] * 32
        current_or = 0
        left = 0
        answer = float('inf')

        def add_number(value: int) -> None:
            nonlocal current_or

            for bit in range(32):
                if value & (1 << bit):
                    bit_count[bit] += 1

                    if bit_count[bit] == 1:
                        current_or |= (1 << bit)

        def remove_number(value: int) -> None:
            nonlocal current_or

            for bit in range(32):
                if value & (1 << bit):
                    bit_count[bit] -= 1

                    if bit_count[bit] == 0:
                        current_or &= ~(1 << bit)

        for right in range(len(nums)):
            add_number(nums[right])

            while left <= right and current_or >= k:
                answer = min(answer, right - left + 1)

                remove_number(nums[left])
                left += 1

        return answer if answer != float('inf') else -1

The implementation begins by handling the simplest edge case. If k == 0, then any non-empty subarray is valid, so the answer is immediately 1.

The bit_count array tracks how many numbers in the current window contain each bit. This is the core data structure that allows efficient OR maintenance.

The add_number helper function updates the bit counts when a new value enters the window. If a bit appears for the first time, that bit is enabled in current_or.

The remove_number helper function reverses the process. When the last occurrence of a bit disappears from the window, that bit is removed from current_or.

The main loop expands the window by moving right. After each expansion, the algorithm checks whether the current OR satisfies the condition.

Whenever the condition is satisfied, the algorithm aggressively shrinks the window from the left. This ensures the shortest valid window ending at the current right index is discovered.

Finally, if no valid subarray exists, the algorithm returns -1.

Go Solution

package main

import "math"

func minimumSubarrayLength(nums []int, k int) int {
	if k == 0 {
		return 1
	}

	bitCount := make([]int, 32)
	currentOR := 0
	left := 0
	answer := math.MaxInt32

	addNumber := func(value int) {
		for bit := 0; bit < 32; bit++ {
			if value&(1<<bit) != 0 {
				bitCount[bit]++

				if bitCount[bit] == 1 {
					currentOR |= (1 << bit)
				}
			}
		}
	}

	removeNumber := func(value int) {
		for bit := 0; bit < 32; bit++ {
			if value&(1<<bit) != 0 {
				bitCount[bit]--

				if bitCount[bit] == 0 {
					currentOR &= ^(1 << bit)
				}
			}
		}
	}

	for right := 0; right < len(nums); right++ {
		addNumber(nums[right])

		for left <= right && currentOR >= k {
			length := right - left + 1

			if length < answer {
				answer = length
			}

			removeNumber(nums[left])
			left++
		}
	}

	if answer == math.MaxInt32 {
		return -1
	}

	return answer
}

The Go implementation follows the same algorithmic structure as the Python version.

One important difference is bit removal syntax. In Go, clearing a bit uses:

currentOR &= ^(1 << bit)

The solution uses closures for addNumber and removeNumber, which keeps the implementation organized and readable.

Since Go does not have Python's float('inf'), the code uses math.MaxInt32 as the sentinel value for the answer.

Worked Examples

Example 1

Input:

nums = [1,2,3]
k = 2

Step-by-step trace

Step	Window	Current OR	Valid?	Best Length
Add 1	[1]	1	No	inf
Add 2	[1,2]	3	Yes	2
Remove 1	[2]	2	Yes	1
Remove 2	[]	0	No	1
Add 3	[3]	3	Yes	1

Final answer:

The shortest valid subarray is [2] or [3].

Example 2

Input:

nums = [2,1,8]
k = 10

Step-by-step trace

Step	Window	Current OR	Valid?	Best Length
Add 2	[2]	2	No	inf
Add 1	[2,1]	3	No	inf
Add 8	[2,1,8]	11	Yes	3
Remove 2	[1,8]	9	No	3

Final answer:

Only the full array reaches OR value 11.

Example 3

Input:

nums = [1,2]
k = 0

Since k = 0, every non-empty subarray is valid.

The shortest possible non-empty subarray has length 1.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(32 × n)	Each element is added and removed once, each operation checks 32 bits
Space	O(32)	Bit frequency array stores counts for 32 bit positions

The algorithm is effectively linear because 32 is a fixed constant. Each number enters and leaves the sliding window at most once, and each operation performs a constant amount of bit manipulation work.

Test Cases

from typing import List

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        if k == 0:
            return 1

        bit_count = [0] * 32
        current_or = 0
        left = 0
        answer = float('inf')

        def add_number(value: int) -> None:
            nonlocal current_or

            for bit in range(32):
                if value & (1 << bit):
                    bit_count[bit] += 1

                    if bit_count[bit] == 1:
                        current_or |= (1 << bit)

        def remove_number(value: int) -> None:
            nonlocal current_or

            for bit in range(32):
                if value & (1 << bit):
                    bit_count[bit] -= 1

                    if bit_count[bit] == 0:
                        current_or &= ~(1 << bit)

        for right in range(len(nums)):
            add_number(nums[right])

            while left <= right and current_or >= k:
                answer = min(answer, right - left + 1)

                remove_number(nums[left])
                left += 1

        return answer if answer != float('inf') else -1

solver = Solution()

assert solver.minimumSubarrayLength([1,2,3], 2) == 1  # single element satisfies
assert solver.minimumSubarrayLength([2,1,8], 10) == 3  # entire array needed
assert solver.minimumSubarrayLength([1,2], 0) == 1  # k = 0 edge case

assert solver.minimumSubarrayLength([8], 8) == 1  # single exact match
assert solver.minimumSubarrayLength([1], 2) == -1  # impossible case

assert solver.minimumSubarrayLength([1,1,1,1], 1) == 1  # repeated values
assert solver.minimumSubarrayLength([1,2,4,8], 15) == 4  # all bits needed

assert solver.minimumSubarrayLength([5,1,1], 5) == 1  # first element alone works
assert solver.minimumSubarrayLength([1,2,7], 7) == 1  # exact OR match
assert solver.minimumSubarrayLength([0,0,0], 1) == -1  # OR never increases

assert solver.minimumSubarrayLength([3,3,3], 2) == 1  # every element valid
assert solver.minimumSubarrayLength([1,2,4], 6) == 2  # middle subarray works

assert solver.minimumSubarrayLength([1 << 30], 1 << 30) == 1  # large bit values

Test Summary

Test	Why
`[1,2,3], k=2`	Basic example with single-element answer
`[2,1,8], k=10`	Entire array required
`[1,2], k=0`	Special edge case where every subarray works
`[8], k=8`	Single-element exact match
`[1], k=2`	No valid subarray exists
`[1,1,1,1], k=1`	Repeated values
`[1,2,4,8], k=15`	Requires combining all bits
`[5,1,1], k=5`	Best answer at beginning
`[1,2,7], k=7`	One element dominates OR
`[0,0,0], k=1`	All-zero failure case
`[3,3,3], k=2`	Every window valid
`[1,2,4], k=6`	Optimal subarray in middle
`[1 << 30], k=1 << 30`	Large bit handling

Edge Cases

Case 1, `k = 0`

This is an important special case because every non-empty subarray automatically satisfies the requirement. Since OR values are always non-negative, the minimum possible answer is always 1.

Without handling this early, the algorithm would still work, but unnecessary processing would occur. The implementation immediately returns 1.

Case 2, No Valid Subarray Exists

Consider:

nums = [0,0,0]
k = 1

The OR of every possible subarray is still 0, so the condition can never be satisfied.

The implementation tracks whether any valid window was discovered using the sentinel value inf. If no update occurs, the algorithm returns -1.

Case 3, Removing Elements Changes Multiple Bits

A subtle challenge arises when shrinking the sliding window.

Suppose the current window OR contains a bit because multiple numbers contribute to it. Removing one number should not necessarily clear the bit.

For example:

Window = [3, 1]
Binary:
3 = 011
1 = 001

The lowest bit is contributed by both numbers.

This is why the implementation uses bit_count. A bit is only removed from current_or when its count drops to zero. This guarantees the OR value always accurately reflects the current window contents.

LeetCode 3097 - Shortest Subarray With OR at Least K II

Solution

LeetCode 3097 - Shortest Subarray With OR at Least K II

Problem Understanding

Approaches

Brute Force

Optimal Approach, Sliding Window with Bit Frequency Counting

Approach Comparison

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step-by-step trace

Example 2

Step-by-step trace

Example 3

Complexity Analysis

Test Cases

Test Summary

Edge Cases

Case 1, k = 0

Case 2, No Valid Subarray Exists

Case 3, Removing Elements Changes Multiple Bits

Case 1, `k = 0`