Shortest Subarray With OR at Least K I

Easy
728.

Shortest Subarray With OR at Least K I

Shortest Subarray With OR at Least K I is an easy coding problem on arrays, bit manipulation and sliding window, asked in Amazon, Adobe and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumSubarrayLength = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Shortest Subarray With OR at Least K I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Shortest Subarray With OR at Least K I is an easy coding problem on arrays, bit manipulation and sliding window, asked in Amazon, Adobe and Zoho interviews.

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

Hints for Shortest Subarray With OR at Least K I

  1. Hint 1

    OR only grows as a subarray is extended, so for a fixed start the first index that reaches k is the best one.

  2. Hint 2

    That makes the double loop with an early break exhaustive and cheap.

  3. Hint 3

    k = 0 is satisfied by any single element.

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

  1. For each start i, reset the running OR to 0.
  2. Extend j from i, OR-ing in nums[j].
  3. The moment the running OR reaches k, record j - i + 1 and break.
  4. 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

Java

public static int minimumSubarrayLength(int[] nums, int k) {
    int best = -1;
    for (int i = 0; i < nums.length; i++) {
        int acc = 0;
        for (int 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;
}

C++

int minimumSubarrayLength(vector<int>& nums, int k) {
    int best = -1;
    int n = (int) nums.size();
    for (int i = 0; i < n; i++) {
        int acc = 0;
        for (int j = i; j < n; j++) {
            acc |= nums[j];
            if (acc >= k) {
                if (best < 0 || 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation