Shortest Subarray With OR at Least K II solution and explanation
Google
9 more videos on this problem
Shortest Subarray With OR at Least K II - Leetcode 3097 - PythonNeetCodeIO · 18:07 · 10K views
Shortest Subarray With OR at Least K II | Made Easy | Detailed | Leetcode 3097 | codestorywithMIKcodestorywithMIK · 34:16 · 9K views
3097. Shortest Subarray With OR at Least K II | Sliding Window | 2 Pointers | Bit ManipulationAryan Mittal · 28:58 · 9K views
Shortest Subarray With OR at Least K II | Leetcode 3097Techdose · 21:13 · 4K views
3097. Shortest Subarray With OR at Least K II | Leetcode Daily (POTD) 10 Nov 2024 | Medium | JavaAlgorithmHQ · 16:54 · 1K views
3097. Shortest Subarray With OR at Least K II | Leetcode Biweekly 127codingMohan · 30:21 · 877 views
3097. Shortest Subarray With OR at Least K II | Sliding WindowTech Courses · 20:38 · 868 views
3097. Shortest Subarray With OR at Least K II (Leetcode Medium)Programming Live with Larry · 20:02 · 613 views
Leetcode 3097 | Shortest Subarray With OR at Least K II | Leetcode Biweekly Contest 127Road To FAANG · 14:04 · 488 views
Leetcode 3097: Shortest Subarray With OR at Least K IIAlgorithms Casts · 19:34 · 283 views
The problem
You are given an array nums of non-negative integers and an integer k.
An array is called special if the bitwise OR of all of its elements is at least k.
Return the length of the shortest special non-empty subarray of nums, or return -1 if no special subarray exists.
Example 1:
Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The subarray [3] has OR value of 3. Hence, we return 1.
Example 2:
Input: nums = [2,1,8], k = 10
Output: 3
Explanation:
The subarray [2,1,8] has OR value of 11. Hence, we return 3.
Example 3:
Input: nums = [1,2], k = 0
Output: 1
Explanation:
The subarray [1] has OR value of 1. Hence, we return 1.
Constraints:
1 <= nums.length <= 2 * 1050 <= nums[i] <= 1090 <= k <= 109
Approach overview
Problem Overview: You are given an integer array nums and an integer k. The task is to find the length of the shortest contiguous subarray whose bitwise OR is at least k. If no such subarray exists, return -1. The challenge comes from maintaining the OR value efficiently while shrinking or expanding the window.
Approach 1: Brute Force Method (Time: O(n^2 * 32), Space: O(1))
The simplest idea is to start a subarray at every index and extend it to the right while maintaining the running OR. For each starting position i, iterate j from i to n-1 and update current_or |= nums[j]. As soon as the OR becomes greater than or equal to k, record the length j - i + 1. Continue this process for every starting index and keep track of the minimum length found. This approach directly explores all subarrays, which leads to quadratic growth in the number of checks. Since integers have up to 32 bits, the OR operation itself is constant time, making the total complexity roughly O(n^2 * 32). This method is useful for validating logic or small input sizes but becomes too slow for large arrays.
Approach 2: Sliding Window with Bit Counting (Time: O(n * 32), Space: O(32))
A more efficient solution uses the sliding window technique combined with bit tracking. The window expands using a right pointer and contracts using a left pointer. The key challenge is that removing an element from a window does not easily update the OR value. To handle this, maintain a frequency array for each bit position (0–31). When a new element enters the window, iterate through its bits and increment the corresponding counters. When an element leaves the window, decrement the counters for the bits it contributed.
At any moment, reconstruct the current OR by checking which bit counters are greater than zero. If the OR becomes at least k, attempt to shrink the window from the left while maintaining the condition. Each element enters and leaves the window at most once, and each update touches at most 32 bits. This results in O(n * 32) time and constant auxiliary space. The method combines ideas from array traversal and bit manipulation to maintain the OR dynamically.
Recommended for interviews: Start by explaining the brute force approach to demonstrate understanding of the subarray search space. Then move to the sliding window optimization. Interviewers expect the optimized version because it handles the difficulty of removing OR contributions using bit counters. This shows you understand both two-pointer window management and bit-level state tracking.
Approach 1: Sliding Window Technique
The sliding window approach allows us to efficiently consider subarrays by expanding and contracting the window size while checking the OR condition. We start by iterating over the array using two pointers that track the start and end of the current window. The objective is to maintain a OR condition that satisfies the requirement of being at least k, while minimizing the window size.
def shortest_subarray_with_or_at_least_k(nums, k):
left, curr_or, min_length = 0, 0, float('inf')
for right in range(len(nums)):
curr_or |= nums[right]
while curr_or >= k and left <= right:
min_length = min(min_length, right - left + 1)
curr_or ^= nums[left]
left += 1
return -1 if min_length == float('inf') else min_length
nums = [1, 2, 3]
k = 2
print(shortest_subarray_with_or_at_least_k(nums, k)) # Output: 1public class ShortestSubarray {
public static int shortestSubarrayWithORAtLeastK(int[] nums, int k) {
int left = 0, currOR = 0, minLength = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; ++right) {
currOR |= nums[right];
while (currOR >= k && left <= right) {
minLength = Math.min(minLength, right - left + 1);
currOR ^= nums[left++];
}
}
return minLength == Integer.MAX_VALUE ? -1 : minLength;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
int k = 2;
System.out.println(shortestSubarrayWithORAtLeastK(nums, k)); // Output: 1
}
}#include <iostream>
#include <vector>
#include <climits>
int shortestSubarrayWithORAtLeastK(const std::vector<int>& nums, int k) {
int left = 0, currOR = 0, minLength = INT_MAX;
for (int right = 0; right < nums.size(); ++right) {
currOR |= nums[right];
while (currOR >= k && left <= right) {
minLength = std::min(minLength, right - left + 1);
currOR ^= nums[left++];
}
}
return minLength == INT_MAX ? -1 : minLength;
}
int main() {
std::vector<int> nums = {1, 2, 3};
int k = 2;
std::cout << shortestSubarrayWithORAtLeastK(nums, k) << std::endl; // Output: 1
return 0;
}function shortestSubarrayWithORAtLeastK(nums, k) {
let left = 0, currOR = 0, minLength = Infinity;
for (let right = 0; right < nums.length; ++right) {
currOR |= nums[right];
while (currOR >= k && left <= right) {
minLength = Math.min(minLength, right - left + 1);
currOR ^= nums[left++];
}
}
return minLength === Infinity ? -1 : minLength;
}
let nums = [1, 2, 3], k = 2;
console.log(shortestSubarrayWithORAtLeastK(nums, k)); // Output: 1#include <stdio.h>
#include <limits.h>
int shortestSubarrayWithORAtLeastK(int* nums, int numsSize, int k) {
int left = 0, currOR = 0, minLength = INT_MAX;
for (int right = 0; right < numsSize; ++right) {
currOR |= nums[right];
while (currOR >= k && left <= right) {
minLength = (right - left + 1) < minLength ? (right - left + 1) : minLength;
currOR ^= nums[left++];
}
}
return minLength == INT_MAX ? -1 : minLength;
}
int main() {
int nums[] = {1, 2, 3};
int k = 2;
printf("%d\n", shortestSubarrayWithORAtLeastK(nums, 3, k)); // Output: 1
return 0;
}using System;
public class ShortestSubarraySolver {
public static int ShortestSubarrayWithORAtLeastK(int[] nums, int k) {
int left = 0, currOR = 0, minLength = int.MaxValue;
for (int right = 0; right < nums.Length; ++right) {
currOR |= nums[right];
while (currOR >= k && left <= right) {
minLength = Math.Min(minLength, right - left + 1);
currOR ^= nums[left++];
}
}
return minLength == int.MaxValue ? -1 : minLength;
}
static void Main() {
int[] nums = {1, 2, 3};
int k = 2;
Console.WriteLine(ShortestSubarrayWithORAtLeastK(nums, k)); // Output: 1
}
}The Python version initializes a variable for the current OR and iterates through the array like previous instances, but using Python's flexible range and list indexing. It uses conditional checks to see if removing the start of the subarray still meets or exceeds the condition.
Time Complexity: O(n), scanning the list once.
Space Complexity: O(1), as no additional structures or sizeable space allocations are needed.
Approach 2: Brute Force Method
The brute force approach involves examining all possible non-empty subarrays. Although this method is not efficient for large inputs, it is a straightforward solution that guarantees finding the result by evaluating each subarray's OR value and checking against the condition.
def shortest_subarray_with_or_at_least_k(nums, k):
min_length = float('inf')
for start in range(len(nums)):
curr_or = 0
for end in range(start, len(nums)):
curr_or |= nums[end]
if curr_or >= k:
min_length = min(min_length, end - start + 1)
break
return -1 if min_length == float('inf') else min_length
nums = [1, 2, 3]
k = 2
print(shortest_subarray_with_or_at_least_k(nums, k)) # Output: 1public class ShortestSubarray {
public static int shortestSubarrayWithORAtLeastK(int[] nums, int k) {
int minLength = Integer.MAX_VALUE;
for (int start = 0; start < nums.length; ++start) {
int currOR = 0;
for (int end = start; end < nums.length; ++end) {
currOR |= nums[end];
if (currOR >= k) {
minLength = Math.min(minLength, end - start + 1);
break;
}
}
}
return minLength == Integer.MAX_VALUE ? -1 : minLength;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
int k = 2;
System.out.println(shortestSubarrayWithORAtLeastK(nums, k)); // Output: 1
}
}#include <iostream>
#include <vector>
#include <climits>
int shortestSubarrayWithORAtLeastK(const std::vector<int>& nums, int k) {
int minLength = INT_MAX;
for (int start = 0; start < nums.size(); ++start) {
int currOR = 0;
for (int end = start; end < nums.size(); ++end) {
currOR |= nums[end];
if (currOR >= k) {
minLength = std::min(minLength, end - start + 1);
break;
}
}
}
return minLength == INT_MAX ? -1 : minLength;
}
int main() {
std::vector<int> nums = {1, 2, 3};
int k = 2;
std::cout << shortestSubarrayWithORAtLeastK(nums, k) << std::endl; // Output: 1
return 0;
}function shortestSubarrayWithORAtLeastK(nums, k) {
let minLength = Infinity;
for (let start = 0; start < nums.length; ++start) {
let currOR = 0;
for (let end = start; end < nums.length; ++end) {
currOR |= nums[end];
if (currOR >= k) {
minLength = Math.min(minLength, end - start + 1);
break;
}
}
}
return minLength === Infinity ? -1 : minLength;
}
let nums = [1, 2, 3], k = 2;
console.log(shortestSubarrayWithORAtLeastK(nums, k)); // Output: 1#include <stdio.h>
#include <limits.h>
int shortestSubarrayWithORAtLeastK(int* nums, int numsSize, int k) {
int minLength = INT_MAX;
for (int start = 0; start < numsSize; ++start) {
int currOR = 0;
for (int end = start; end < numsSize; ++end) {
currOR |= nums[end];
if (currOR >= k) {
minLength = (end - start + 1) < minLength ? (end - start + 1) : minLength;
break;
}
}
}
return minLength == INT_MAX ? -1 : minLength;
}
int main() {
int nums[] = {1, 2, 3};
int k = 2;
printf("%d\n", shortestSubarrayWithORAtLeastK(nums, 3, k)); // Output: 1
return 0;
}using System;
public class ShortestSubarraySolver {
public static int ShortestSubarrayWithORAtLeastK(int[] nums, int k) {
int minLength = int.MaxValue;
for (int start = 0; start < nums.Length; ++start) {
int currOR = 0;
for (int end = start; end < nums.Length; ++end) {
currOR |= nums[end];
if (currOR >= k) {
minLength = Math.Min(minLength, end - start + 1);
break;
}
}
}
return minLength == int.MaxValue ? -1 : minLength;
}
static void Main() {
int[] nums = {1, 2, 3};
int k = 2;
Console.WriteLine(ShortestSubarrayWithORAtLeastK(nums, k)); // Output: 1
}
}Aimed at known subarray evaluations, this Python brute force solution examines every potential subarray OR total, logging the minimum length that satisfies k. The nested loop structure identifies all start-point possibilities and computes correspondingly.
Time Complexity: O(n^2), due to nested pairings.
Space Complexity: O(1), only involving initial variable storage.
Approach 3: Two Pointers + Counting
We can observe that if we fix the left endpoint of the subarray, as the right endpoint moves to the right, the bitwise OR value of the subarray will only increase, not decrease. Therefore, we can use the double pointers method to maintain a subarray that meets the conditions.
Specifically, we use two pointers i and j to represent the left and right endpoints of the subarray, respectively. Initially, both pointers are at the first element of the array. We use a variable s to represent the bitwise OR value of the subarray, and initially, the value of s is 0. We also need to maintain an array cnt of length 32, which represents the occurrence times of each bit in the binary representation of each element in the subarray.
In each step, we move j to the right by one position, and update s and cnt. If the value of s is greater than or equal to k, we continuously update the minimum length of the subarray and move i to the right by one position until the value of s is less than k. In this process, we also need to update s and cnt.
Finally, we return the minimum length. If there is no subarray that meets the conditions, we return -1.
The time complexity is O(n times log M) and the space complexity is O(log M), where n and M are the length of the array and the maximum value of the elements in the array, respectively.
Similar Problems:
function minimumSubarrayLength(nums: number[], k: number): number {
const n = nums.length;
let ans = n + 1;
const cnt: number[] = new Array<number>(32).fill(0);
for (let i = 0, j = 0, s = 0; j < n; ++j) {
s |= nums[j];
for (let h = 0; h < 32; ++h) {
if (((nums[j] >> h) & 1) === 1) {
++cnt[h];
}
}
for (; s >= k && i <= j; ++i) {
ans = Math.min(ans, j - i + 1);
for (let h = 0; h < 32; ++h) {
if (((nums[i] >> h) & 1) === 1 && --cnt[h] === 0) {
s ^= 1 << h;
}
}
}
}
return ans === n + 1 ? -1 : ans;
}func minimumSubarrayLength(nums []int, k int) int {
n := len(nums)
cnt := [32]int{}
ans := n + 1
s, i := 0, 0
for j, x := range nums {
s |= x
for h := 0; h < 32; h++ {
if x>>h&1 == 1 {
cnt[h]++
}
}
for ; s >= k && i <= j; i++ {
ans = min(ans, j-i+1)
for h := 0; h < 32; h++ {
if nums[i]>>h&1 == 1 {
cnt[h]--
if cnt[h] == 0 {
s ^= 1 << h
}
}
}
}
}
if ans == n+1 {
return -1
}
return ans
}impl Solution {
pub fn minimum_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let mut cnt = vec![0; 32];
let mut ans = n as i32 + 1;
let mut s = 0;
let mut i = 0;
for (j, &x) in nums.iter().enumerate() {
s |= x;
for h in 0..32 {
if (x >> h) & 1 == 1 {
cnt[h] += 1;
}
}
while s >= k && i <= j {
ans = ans.min((j - i + 1) as i32);
let y = nums[i];
for h in 0..32 {
if (y >> h) & 1 == 1 {
cnt[h] -= 1;
if cnt[h] == 0 {
s ^= 1 << h;
}
}
}
i += 1;
}
}
if ans > n as i32 { -1 } else { ans }
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n), scanning the list once. |
| Brute Force Method | Time Complexity: O(n^2), due to nested pairings. |
| Two Pointers + Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Scan | O(n^2 * 32) | O(1) | Small input sizes or when verifying correctness before optimizing |
| Sliding Window with Bit Counters | O(n * 32) | O(32) | General case and optimal solution for large arrays |
Frequently asked questions
Is Shortest Subarray With OR at Least K II easy or hard?
Shortest Subarray With OR at Least K II is generally rated Medium difficulty. The main challenge is realizing that bitwise OR cannot be easily reversed when removing elements, which requires tracking bit frequencies to maintain the window efficiently.
Shortest Subarray With OR at Least K II Python/Java solution
Most implementations follow the same idea across languages: maintain two pointers and a 32-length bit counter array. Update counters when expanding or shrinking the window and recompute the OR from active bits. The logic translates directly to Python, Java, C++, C, C#, and JavaScript.
How to solve Shortest Subarray With OR at Least K II in O(n)?
Use a sliding window and maintain a count of set bits for every position from 0 to 31. When a number enters the window, increment the counters for its set bits; when it leaves, decrement them. Reconstruct the OR value from these counters and shrink the window whenever the OR is at least k. Each index is processed a constant number of times, leading to O(n * 32) complexity, which is effectively linear.
What is the best approach for Shortest Subarray With OR at Least K II?
The optimal approach uses a sliding window combined with bit counting. Maintain a frequency array for the 32 bit positions to track which bits exist in the current window. Expand the window with a right pointer and shrink it with a left pointer while recomputing the OR from active bits. This achieves O(n * 32) time and O(32) space.
Is Shortest Subarray With OR at Least K II asked at Google/Amazon/Meta?
Problems combining sliding window and bit manipulation frequently appear in interviews at companies like Amazon, Google, and Meta. Variations that require maintaining bitwise OR or AND over a dynamic window are common because they test both two-pointer reasoning and bit-level thinking.
What data structure is used in Shortest Subarray With OR at Least K II?
The main structure is a sliding window implemented with two pointers. A fixed-size array of length 32 stores the frequency of each bit position in the window. This allows efficient updates when elements are added or removed and helps reconstruct the current OR value quickly.
What is the time complexity of Shortest Subarray With OR at Least K II?
The optimized sliding window solution runs in O(n * 32) time because each element enters and leaves the window once and each update checks up to 32 bits. The brute force approach takes O(n^2 * 32) time since it evaluates all possible subarrays.