Shortest Subarray With OR at Least K I solution and explanation
4 more videos on this problem
3095. and 3097. Shortest Subarray With OR at Least K I and II || Leetcode || Biweekly contest 127Ashish Kumar · 18:55 · 731 views
3095. Shortest Subarray With OR at Least K I (Leetcode Easy)Programming Live with Larry · 5:11 · 706 views
💫𝑩𝒊𝒘𝒆𝒆𝒌𝒍𝒚 𝑪𝒐𝒏𝒕𝒆𝒔𝒕 𝟭𝟮𝟳 𝑷𝒓𝒐𝒃𝒍𝒆𝒎 1: 𝟯𝟬𝟵𝟱. 𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕 𝑺𝒖𝒃𝒂𝒓𝒓𝒂𝒚 𝑾𝒊𝒕𝒉 𝑶𝑹 𝒂𝒕 𝑳𝒆𝒂𝒔𝒕 𝑲 𝑰 || 𝑳𝒆𝒆𝒕𝒄𝒐𝒅𝒆Achyuth Chowdary · 3:55 · 166 views
#LeetCode 3095 | Shortest Subarray With OR at Least K I #JavaSleepy Cracker · 5:30 · 89 views
Leetcode easy problem 3095. Shortest Subarray With OR at Least K I | devops python practiceADevOpsEngineer · 12:33 · 15 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.
Note that [2] is also a special subarray.
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 <= 500 <= nums[i] <= 500 <= k < 64
Approach overview
Problem Overview: You are given an integer array nums and a value k. The task is to find the length of the shortest non-empty subarray whose bitwise OR is greater than or equal to k. If no such subarray exists, return -1. The challenge comes from the behavior of the bitwise OR operation: once a bit becomes 1, it stays 1 when more elements are added.
Approach 1: Brute Force Enumeration (O(n² * 32) time, O(1) space)
Start every subarray from index i and expand the end pointer j one element at a time. Maintain a running OR value as you extend the subarray using current_or |= nums[j]. After each expansion, check whether current_or >= k. Once the condition is satisfied, update the minimum length and stop extending that start index because any longer subarray will only increase the length. The complexity becomes O(n²) in the worst case, with a constant factor related to bit operations (up to 32 bits for integers). This approach is simple and good for understanding how OR accumulates across a range.
Approach 2: Sliding Window with Bit Counters (O(n * 32) time, O(32) space)
The optimal solution uses a sliding window combined with bit manipulation. The window expands with a right pointer and shrinks with a left pointer. The key difficulty is that removing an element from a window does not directly undo the OR operation. To handle this, maintain an array of size 32 where each index counts how many numbers in the current window contribute that bit.
When you add a number, iterate through its bits and increment the corresponding counters. Reconstruct the current OR value by checking which bit counters are non-zero. If the OR becomes at least k, attempt to shrink the window from the left while maintaining the condition. When removing a number, decrement its bit counters and recompute the OR accordingly. Each element enters and leaves the window once, and each update processes up to 32 bits, resulting in O(n * 32) time and O(32) extra space.
This approach works well because the OR value only depends on whether at least one element contributes a bit. Tracking frequencies allows the window to both grow and shrink efficiently while preserving correctness.
Recommended for interviews: Start by explaining the brute force enumeration to demonstrate understanding of how bitwise OR accumulates across subarrays. Then move to the optimized sliding window solution. Interviewers typically expect the O(n * 32) approach because it combines array traversal, two pointers, and bit tracking to efficiently maintain the OR value while shrinking the window.
Approach 1: Brute Force Approach
The brute force approach explores all possible subarrays, calculates the OR value of each subarray, and keeps track of the shortest one that meets the condition, where the OR value is at least k.
For each subarray, traverse from the start until the end of the subarray, compute the OR value step-by-step, and compare it with k. Update the shortest length whenever you find a valid subarray.
def shortestSubarray(nums, k):
minLength = float('inf')
for start in range(len(nums)):
orValue = 0
for end in range(start, len(nums)):
orValue |= nums[end]
if orValue >= k:
minLength = min(minLength, end - start + 1)
break
return -1 if minLength == float('inf') else minLength
# Example usage
nums = [1, 2, 3]
k = 2
print(shortestSubarray(nums, k))class Solution {
public int shortestSubarray(int[] nums, int k) {
int minLength = Integer.MAX_VALUE;
for (int start = 0; start < nums.length; start++) {
int orValue = 0;
for (int end = start; end < nums.length; end++) {
orValue |= nums[end];
if (orValue >= k) {
minLength = Math.min(minLength, end - start + 1);
break;
}
}
}
return minLength == Integer.MAX_VALUE ? -1 : minLength;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3};
int k = 2;
System.out.println(sol.shortestSubarray(nums, k));
}
}#include <iostream>
#include <vector>
#include <limits>
int shortestSubarray(std::vector<int>& nums, int k) {
int minLength = std::numeric_limits<int>::max();
for (int start = 0; start < nums.size(); ++start) {
int orValue = 0;
for (int end = start; end < nums.size(); ++end) {
orValue |= nums[end];
if (orValue >= k) {
minLength = std::min(minLength, end - start + 1);
break;
}
}
}
return minLength == std::numeric_limits<int>::max() ? -1 : minLength;
}
int main() {
std::vector<int> nums = {1, 2, 3};
int k = 2;
std::cout << shortestSubarray(nums, k) << std::endl;
return 0;
}function shortestSubarray(nums, k) {
let minLength = Infinity;
for (let start = 0; start < nums.length; start++) {
let orValue = 0;
for (let end = start; end < nums.length; end++) {
orValue |= nums[end];
if (orValue >= k) {
minLength = Math.min(minLength, end - start + 1);
break;
}
}
}
return minLength === Infinity ? -1 : minLength;
}
// Example usage
let nums = [1, 2, 3];
let k = 2;
console.log(shortestSubarray(nums, k));#include <stdio.h>
#include <limits.h>
int shortestSubarray(int* nums, int numsSize, int k) {
int minLength = INT_MAX;
for (int start = 0; start < numsSize; start++) {
int orValue = 0;
for (int end = start; end < numsSize; end++) {
orValue |= nums[end];
if (orValue >= 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;
int result = shortestSubarray(nums, 3, k);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int ShortestSubarray(int[] nums, int k) {
int minLength = int.MaxValue;
for (int start = 0; start < nums.Length; start++) {
int orValue = 0;
for (int end = start; end < nums.Length; end++) {
orValue |= nums[end];
if (orValue >= k) {
minLength = Math.Min(minLength, end - start + 1);
break;
}
}
}
return minLength == int.MaxValue ? -1 : minLength;
}
public static void Main(string[] args) {
int[] nums = {1, 2, 3};
int k = 2;
Solution sol = new Solution();
Console.WriteLine(sol.ShortestSubarray(nums, k));
}
}The Python implementation employs nested loops like in C and C++, iterating over potential starting and ending indices to calculate OR value dynamically. The shortest subarray that fulfills the condition updates the minLength variable. This approach handles edge cases by checking if k is not exceeded.
Time Complexity: O(n^2) - Evaluating all subarray spans for the OR operation.
Space Complexity: O(1) - Space complexity is minimal with constant extra variables.
Approach 2: Optimized Sliding Window Approach
Using a sliding window mechanism helps to efficiently manage subarrays. The core idea is to apply a dynamic window, expanding until achieving a valid OR value, and then gradually shrinking to find the minimal length subarray.
This method allows efficient optimizations by avoiding redundant recalculations and systematically reducing excessive subarray spans, simplifying the process compared to the exhaustive search.
def shortestSubarray(nums, k):
minLength = float('inf')
orValue = 0
start = 0
for end in range(len(nums)):
orValue |= nums[end]
while orValue >= k:
minLength = min(minLength, end - start + 1)
orValue ^= nums[start]
start += 1
return -1 if minLength == float('inf') else minLength
# Example usage
nums = [1, 2, 3]
k = 2
print(shortestSubarray(nums, k))class Solution {
public int shortestSubarray(int[] nums, int k) {
int minLength = Integer.MAX_VALUE;
int orValue = 0;
for (int start = 0, end = 0; end < nums.length; end++) {
orValue |= nums[end];
while (orValue >= k) {
minLength = Math.min(minLength, end - start + 1);
orValue ^= nums[start++];
}
}
return minLength == Integer.MAX_VALUE ? -1 : minLength;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3};
int k = 2;
System.out.println(sol.shortestSubarray(nums, k));
}
}#include <iostream>
#include <vector>
#include <limits>
int shortestSubarray(std::vector<int>& nums, int k) {
int minLength = std::numeric_limits<int>::max();
int orValue = 0;
for (int start = 0, end = 0; end < nums.size(); ++end) {
orValue |= nums[end];
while (orValue >= k) {
minLength = std::min(minLength, end - start + 1);
orValue ^= nums[start++];
}
}
return minLength == std::numeric_limits<int>::max() ? -1 : minLength;
}
int main() {
std::vector<int> nums = {1, 2, 3};
int k = 2;
std::cout << shortestSubarray(nums, k) << std::endl;
return 0;
}function shortestSubarray(nums, k) {
let minLength = Infinity;
let orValue = 0;
for (let start = 0, end = 0; end < nums.length; end++) {
orValue |= nums[end];
while (orValue >= k) {
minLength = Math.min(minLength, end - start + 1);
orValue ^= nums[start++];
}
}
return minLength === Infinity ? -1 : minLength;
}
// Example usage
let nums = [1, 2, 3];
let k = 2;
console.log(shortestSubarray(nums, k));#include <stdio.h>
#include <limits.h>
int shortestSubarray(int* nums, int numsSize, int k) {
int minLength = INT_MAX;
int orValue = 0;
for (int start = 0, end = 0; end < numsSize; end++) {
orValue |= nums[end];
while (orValue >= k) {
minLength = (end - start + 1) < minLength ? (end - start + 1) : minLength;
orValue ^= nums[start++];
}
}
return minLength == INT_MAX ? -1 : minLength;
}
int main() {
int nums[] = {1, 2, 3};
int k = 2;
int result = shortestSubarray(nums, 3, k);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int ShortestSubarray(int[] nums, int k) {
int minLength = int.MaxValue;
int orValue = 0;
for (int start = 0, end = 0; end < nums.Length; end++) {
orValue |= nums[end];
while (orValue >= k) {
minLength = Math.Min(minLength, end - start + 1);
orValue ^= nums[start++];
}
}
return minLength == int.MaxValue ? -1 : minLength;
}
public static void Main(string[] args) {
int[] nums = {1, 2, 3};
int k = 2;
Solution sol = new Solution();
Console.WriteLine(sol.ShortestSubarray(nums, k));
}
}The Python approach maintains a sliding window by managing two pointers across the list, continuously analyzing the cumulative OR and optimizing the subarray’s span. This reduces redundant calculations while upholding logic and effectiveness.
Time Complexity: O(n) - Elements are systematically analyzed with efficient windowing.
Space Complexity: O(1) - Limited extra space used beyond algorithms and inputs.
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.
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 |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) - Evaluating all subarray spans for the OR operation. |
| Optimized Sliding Window Approach | Time Complexity: O(n) - Elements are systematically analyzed with efficient windowing. |
| Two Pointers + Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Expansion | O(n² * 32) | O(1) | Good for understanding the OR accumulation behavior or when input size is small |
| Sliding Window with Bit Counters | O(n * 32) | O(32) | Optimal for large arrays; maintains OR dynamically while shrinking the window |
Frequently asked questions
Is Shortest Subarray With OR at Least K I easy or hard?
The problem is labeled Easy but can feel closer to Medium if you have not handled sliding windows with bit manipulation before. The brute force approach is straightforward, while the optimized method requires tracking bit contributions to correctly update the OR when shrinking the window.
Shortest Subarray With OR at Least K I Python/Java solution
Most implementations use a sliding window and a 32-length bit counter array. Python, Java, C++, and C# solutions iterate through bits using shifts like (num >> bit) & 1 to update counters and rebuild the OR when shrinking the window.
How to solve Shortest Subarray With OR at Least K I in O(n)?
Use a sliding window with bit counting. Track how many numbers in the window contribute to each of the 32 bit positions. When the window expands, update bit counts and recompute the OR. When the OR is at least k, move the left pointer to minimize the window while updating bit counters. Each element enters and exits the window once, resulting in linear scanning with a small constant factor.
What is the best approach for Shortest Subarray With OR at Least K I?
The most efficient approach uses a sliding window combined with bit counters. Maintain a frequency array for the 32 bits of integers and track which bits are active in the current window. Expand the window until the OR value reaches at least k, then shrink it from the left while preserving the condition. This achieves O(n * 32) time and O(32) space.
Is Shortest Subarray With OR at Least K I asked at Google/Amazon/Meta?
Bit manipulation combined with sliding window techniques frequently appears in interviews at companies like Amazon, Google, and Meta. Variants of subarray OR or AND problems are common because they test understanding of bit operations and two-pointer optimization.
What data structure is used in Shortest Subarray With OR at Least K I?
The optimized solution primarily uses an array of size 32 to count how many numbers contribute to each bit position. This structure allows efficient updates when elements enter or leave the sliding window and helps reconstruct the current OR value.
What is the time complexity of Shortest Subarray With OR at Least K I?
The brute force method runs in O(n² * 32) time because every subarray may be explored while updating the OR value. The optimized sliding window solution processes each element once while updating up to 32 bits, giving O(n * 32) time complexity with constant extra space.