Shortest Subarray With OR at Least K II

Medium
1366.

Shortest Subarray With OR at Least K II

Shortest Subarray With OR at Least K II is a medium coding problem on arrays, bit manipulation and sliding window, asked in Amazon and Google interviews.

You are given an array nums of non-negative integers and an integer k.

A non-empty contiguous subarray is special when the bitwise OR of all its elements is at least k.

Return the length of the shortest special subarray, or -1 if no subarray is special.

Example 1

Input
nums = [1,4,2,8], k = 12
Output
3
Explanation
`[4,2,8]` has OR 14. No single element or pair reaches 12 (the best pair, `[2,8]`, gives 10).

Example 2

Input
nums = [5,3], k = 8
Output
-1
Explanation
Even the whole array only reaches 5 | 3 = 7.

Example 3

Input
nums = [0,0,6], k = 0
Output
1
Explanation
With `k = 0` any single element works.

Constraints

  • 1 <= nums.length <= 2 * 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 10^9
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 II — Problem & Solution

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

Shortest Subarray With OR at Least K II is a medium coding problem on arrays, bit manipulation and sliding window, asked in Amazon and Google interviews.

Problem statement

You are given an array nums of non-negative integers and an integer k.

A non-empty contiguous subarray is special when the bitwise OR of all its elements is at least k.

Return the length of the shortest special subarray, or -1 if no subarray is special.

Example 1

Input: nums = [1,4,2,8], k = 12
Output: 3
Explanation: `[4,2,8]` has OR 14. No single element or pair reaches 12 (the best pair, `[2,8]`, gives 10).

Example 2

Input: nums = [5,3], k = 8
Output: -1
Explanation: Even the whole array only reaches 5 | 3 = 7.

Example 3

Input: nums = [0,0,6], k = 0
Output: 1
Explanation: With `k = 0` any single element works.

Constraints

  • 1 <= nums.length <= 2 * 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

Hints for Shortest Subarray With OR at Least K II

  1. Hint 1

    OR never decreases when a subarray grows. So if a window is special, every window containing it is special too.

  2. Hint 2

    That monotonicity allows a sliding window: extend on the right, and while the window is special record its length and shrink from the left.

  3. Hint 3

    OR cannot be "undone" when an element leaves. Keep, for each of the 30 bit positions, how many elements in the window have that bit set; the window's OR is the set of bits with a non-zero count.

How to solve Shortest Subarray With OR at Least K II

OR is monotone under extension, which makes the shortest special window findable with two pointers. Removing an element from an OR needs per-bit counters.

Approach

  1. Keep cnt[b] = number of window elements with bit b set, for b = 0..30, and left = 0.
  2. For each right, add nums[right]'s bits to cnt.
  3. While left <= right and the window's OR (bits with cnt[b] > 0) is at least k: record right - left + 1, subtract nums[left]'s bits, advance left.
  4. Return the smallest recorded length, or -1 if none.

Why it works

For each right end, the loop shrinks the window to the shortest special window ending there (or stops at the first non-special one). Since a special window stays special when extended to the right, the shortest special window for the next right end cannot start before the current left, so left never needs to move back. The per-bit counters make the OR of the current window exact after every removal.

Complexity

  • Time — O(30 · n)
  • Space — O(30)

Pitfalls

  • Keeping a single running OR and "subtracting" with XOR or AND-NOT is wrong — another element may share the bit.
  • k = 0 means every non-empty subarray is special: the answer is 1.
  • Values are below 2^30, so 30 or 31 bit counters suffice; rebuilding the OR from them is O(30) per step.

Reference solution

Python

from typing import List

def minimumSubarrayLength(nums: List[int], k: int) -> int:
    cnt = [0] * 31
    n = len(nums)
    best = n + 1
    left = 0

    def current() -> int:
        v = 0
        for b in range(31):
            if cnt[b] > 0:
                v |= 1 << b
        return v

    for right in range(n):
        x = nums[right]
        for b in range(31):
            if (x >> b) & 1:
                cnt[b] += 1
        while left <= right and current() >= k:
            best = min(best, right - left + 1)
            y = nums[left]
            for b in range(31):
                if (y >> b) & 1:
                    cnt[b] -= 1
            left += 1
    return -1 if best > n else best

Java

public static int minimumSubarrayLength(int[] nums, int k) {
    int[] cnt = new int[31];
    int n = nums.length, best = n + 1, left = 0;
    for (int right = 0; right < n; right++) {
        for (int b = 0; b < 31; b++) if (((nums[right] >> b) & 1) == 1) cnt[b]++;
        while (left <= right) {
            int cur = 0;
            for (int b = 0; b < 31; b++) if (cnt[b] > 0) cur |= 1 << b;
            if (cur < k) break;
            best = Math.min(best, right - left + 1);
            for (int b = 0; b < 31; b++) if (((nums[left] >> b) & 1) == 1) cnt[b]--;
            left++;
        }
    }
    return best > n ? -1 : best;
}

C++

int minimumSubarrayLength(vector<int>& nums, int k) {
    int cnt[31] = {0};
    int n = nums.size(), best = n + 1, left = 0;
    for (int right = 0; right < n; right++) {
        for (int b = 0; b < 31; b++) if ((nums[right] >> b) & 1) cnt[b]++;
        while (left <= right) {
            int cur = 0;
            for (int b = 0; b < 31; b++) if (cnt[b] > 0) cur |= 1 << b;
            if (cur < k) break;
            best = min(best, right - left + 1);
            for (int b = 0; b < 31; b++) if ((nums[left] >> b) & 1) cnt[b]--;
            left++;
        }
    }
    return best > n ? -1 : best;
}

JavaScript

var minimumSubarrayLength = function(nums, k) {
    var cnt = new Array(31).fill(0);
    var n = nums.length, best = n + 1, left = 0;
    var current = function() {
        var v = 0;
        for (var b = 0; b < 31; b++) if (cnt[b] > 0) v |= (1 << b);
        return v;
    };
    for (var right = 0; right < n; right++) {
        for (var b = 0; b < 31; b++) if ((nums[right] >> b) & 1) cnt[b]++;
        while (left <= right && current() >= k) {
            if (right - left + 1 < best) best = right - left + 1;
            for (var c = 0; c < 31; c++) if ((nums[left] >> c) & 1) cnt[c]--;
            left++;
        }
    }
    return best > n ? -1 : 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