Shortest Subarray With OR at Least K I — Easy Problem & Solution

A subarray is special when the bitwise OR of its elements is at least k. Return the length of the shortest special subarray, or -1 if none exists.

Difficulty: Easy
Topics: Arrays, Bit Manipulation, Sliding Window
Asked at: Amazon, Adobe, Zoho
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A subarray is special when the bitwise OR of its elements is at least k.

Return the length of the shortest special subarray, or -1 if none exists.

Example 1

Input: nums = [1,2,3], k = 2
Output: 1
Explanation: The single element 2 already reaches 2.

Example 2

Input: nums = [2,1,8], k = 10
Output: 3
Explanation: Only the whole array ORs to 11.

Example 3

Input: nums = [1,2], k = 0
Output: 1
Explanation: Any subarray ORs to at least 0.

Constraints

1 <= nums.length <= 50
0 <= nums[i] < 64
0 <= k < 64

How to solve Shortest Subarray With OR at Least K I

Bitwise OR is monotone under extension — adding elements can only set more bits. So for each starting index, extend until the running OR reaches k and stop; that is the shortest special subarray starting there.

Approach

For each start i, reset the running OR to 0.
Extend j from i, OR-ing in nums[j].
The moment the running OR reaches k, record j - i + 1 and break.
Return the smallest length recorded, or -1.

Why it works

Because OR never decreases as the window grows, once a start reaches k no longer window from that start can be shorter — so breaking is safe and every candidate minimum is examined.

Complexity

Time — O(n²)
Space — O(1)

Pitfalls

Not resetting the accumulator between starts leaks bits from earlier windows.
k = 0 must return 1, not 0 — the subarray has to be non-empty.
A true sliding window needs per-bit counters, since OR cannot be undone by removing an element.

Reference solution

Python

from typing import List

def minimumSubarrayLength(nums: List[int], k: int) -> int:
    best = -1
    for i in range(len(nums)):
        acc = 0
        for j in range(i, len(nums)):
            acc |= nums[j]
            if acc >= k:
                if best < 0 or j - i + 1 < best:
                    best = j - i + 1
                break
    return best

JavaScript

var minimumSubarrayLength = function(nums, k) {
    var best = -1;
    for (var i = 0; i < nums.length; i++) {
        var acc = 0;
        for (var j = i; j < nums.length; j++) {
            acc |= nums[j];
            if (acc >= k) {
                if (best < 0 || j - i + 1 < best) best = j - i + 1;
                break;
            }
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue