Shortest Subarray With OR at Least K I - Solution & Explanation
Problem Statement
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.
This C code iterates over all possible subarrays using two nested loops. It calculates the OR of elements from the starting point to the current endpoint and checks if the resultant OR is at least k. The minimal length for the satisfying subarrays is stored, updating only when a valid subarray is found.
Complexity
Time Complexity: O(n^2) - All pairs of start and end indices are traversed for OR calculation.
Space Complexity: O(1) - No additional space is required besides input handling.
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.
This C code employs a sliding window approach. Two pointers (start, end) are used to manage a dynamic window. The orValue is calculated iteratively while managing the window size to ensure it's minimal. When the minimal OR condition is met, the start position moves rightward to shrink the window, optimizing operations.
Complexity
Time Complexity: O(n) - Each element is processed at most twice due to the sliding window strategy.
Space Complexity: O(1) - Only pointers and basic elements/constants used outside sequence 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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) - All pairs of start and end indices are traversed for OR calculation. |
| Optimized Sliding Window Approach | Time Complexity: O(n) - Each element is processed at most twice due to the sliding window strategy. |
| Two Pointers + Counting | — |
Detailed 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 |
Video Solution
3095. and 3097. Shortest Subarray With OR at Least K I and II || Leetcode || Biweekly contest 127 • Ashish Kumar • 731 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Shortest Subarray With OR at Least K I easy or hard?
Shortest Subarray With OR at Least K I Python/Java solution
How to solve Shortest Subarray With OR at Least K I in O(n)?
What is the best approach for Shortest Subarray With OR at Least K I?
Is Shortest Subarray With OR at Least K I asked at Google/Amazon/Meta?
What data structure is used in Shortest Subarray With OR at Least K I?
What is the time complexity of Shortest Subarray With OR at Least K I?
Ready to solve this problem?
Practice Shortest Subarray With OR at Least K I with our built-in code editor and test cases.
Practice on FleetCode