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.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Sliding Window
- Asked at: Amazon, Google
- 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
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^50 <= nums[i] <= 10^90 <= k <= 10^9
Hints for Shortest Subarray With OR at Least K II
Hint 1
OR never decreases when a subarray grows. So if a window is special, every window containing it is special too.
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.
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
- Keep
cnt[b]= number of window elements with bitbset, forb = 0..30, andleft = 0. - For each
right, addnums[right]'s bits tocnt. - While
left <= rightand the window's OR (bits withcnt[b] > 0) is at leastk: recordright - left + 1, subtractnums[left]'s bits, advanceleft. - Return the smallest recorded length, or
-1if 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 = 0means 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 bestJava
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