Shortest Subarray With OR at Least K II
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach systematically checks every possible non-empty subarray within the nums array. For each subarray, it calculates the bitwise OR of its elements and checks if this value is at least k. It keeps track of the minimum length of such a subarray found so far.
Algorithm
- Initialize
minLengthto a value larger than any possible subarray length, likenums.length + 1. - Iterate through the array with an index
ifrom0ton-1, representing the start of a subarray. - For each
i, start a nested loop with an indexjfromiton-1, representing the end of the subarray. - Maintain a variable
currentOrfor the subarraynums[i...j]. Initialize it to0before the inner loop. - In the inner loop, update
currentOrby ORing it withnums[j]:currentOr |= nums[j]. - After updating, check if
currentOr >= k. - If the condition is met, you've found a special subarray of length
j - i + 1. UpdateminLength = min(minLength, j - i + 1). - As an optimization, since we are looking for the shortest subarray, once a special subarray starting at
iis found, any longer subarray starting atiis not of interest. So, we canbreakthe inner loop and proceed to the next starting indexi. - After the loops complete, if
minLengthis still its initial large value, it means no special subarray was found. Return-1. - Otherwise, return
minLength.
Walkthrough
The brute-force method iterates through all possible start and end points of a subarray. A naive implementation would re-calculate the OR for each subarray from scratch, leading to an O(N^3) complexity. However, this can be easily optimized. For a fixed starting point i, we can extend the subarray by moving the endpoint j from i to the end of the array. The bitwise OR of the new, longer subarray nums[i...j] can be calculated in O(1) time from the OR of the previous subarray nums[i...j-1]. This optimization reduces the complexity to O(N^2).
class Solution { public int shortestSubarray(int[] nums, int k) { int n = nums.length; int minLength = n + 1; for (int i = 0; i < n; i++) { int currentOr = 0; for (int j = i; j < n; j++) { currentOr |= nums[j]; if (currentOr >= k) { minLength = Math.min(minLength, j - i + 1); // Optimization: once we find a valid subarray starting at i, // any longer one is not needed for the shortest length. break; } } } return minLength > n ? -1 : minLength; }}Complexity
Time
O(N^2), where N is the number of elements in `nums`. There are two nested loops to iterate through all subarrays starting at `i`.
Space
O(1) extra space, as we only use a few variables to store the minimum length and the current OR value.
Trade-offs
Pros
Simple to understand and implement.
It's a good starting point for developing more efficient solutions.
Cons
The time complexity of O(N^2) is too slow for the given constraints (N up to 2 * 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
A more efficient solution uses the sliding window technique. A standard sliding window is hard to apply directly because removing an element from the left of the window (to calculate the new OR) is not a simple operation. To overcome this, we can maintain the count of set bits for each bit position (0 to 30) within the current window. This allows us to efficiently add and remove elements while keeping track of the window's total bitwise OR.
Algorithm
- Initialize
minLengthtonums.length + 1, aleftpointer to0, and an integer arraybitCountsof size 31 to all zeros. This array will track the number of elements in the current window that have a specific bit set. - Iterate through the array with a
rightpointer from0ton-1. - For each element
nums[right], 'add' it to the sliding window. This is done by iterating from bit0to30and incrementingbitCounts[p]if thep-th bit is set innums[right]. - After expanding the window to include
nums[right], enter awhileloop that checks if the current window[left, right]is 'special' and tries to shrink it from the left. - Inside the
whileloop, first calculate thecurrentOrof the window[left, right]by checkingbitCounts. IfbitCounts[p] > 0, thep-th bit is set incurrentOr. - If
currentOr >= k:- The window is special. Update
minLength = min(minLength, right - left + 1). - Shrink the window from the left: 'remove'
nums[left]by decrementing the corresponding counts inbitCounts, and then increment theleftpointer.
- The window is special. Update
- If
currentOr < k:- The window is not special. We cannot shrink it further and still satisfy the condition.
breakthewhileloop and continue expanding the window by incrementingright.
- The window is not special. We cannot shrink it further and still satisfy the condition.
- After the main loop finishes, if
minLengthhas not been updated, return-1. Otherwise, returnminLength.
Walkthrough
This approach maintains a sliding window [left, right] and a bitCounts array. The bitCounts[p] entry stores how many numbers in the current window have the p-th bit set. As we slide the window's right boundary, we update bitCounts. Then, we check if the window's OR value (which can be reconstructed from bitCounts) is at least k. If it is, we've found a candidate subarray. We then try to shrink the window from the left, updating bitCounts accordingly, to find the smallest possible valid window ending at the current right position. This process ensures that for each right, we find the shortest valid subarray ending at right.
class Solution { public int shortestSubarray(int[] nums, int k) { int n = nums.length; int minLength = n + 1; int left = 0; int[] bitCounts = new int[31]; for (int right = 0; right < n; right++) { // Add nums[right] to the window by updating bit counts for (int i = 0; i < 31; i++) { if (((nums[right] >> i) & 1) == 1) { bitCounts[i]++; } } // While the window is valid, update minLength and shrink from the left while (left <= right) { int currentOr = 0; for (int i = 0; i < 31; i++) { if (bitCounts[i] > 0) { currentOr |= (1 << i); } } if (currentOr >= k) { minLength = Math.min(minLength, right - left + 1); // Shrink window from the left for (int i = 0; i < 31; i++) { if (((nums[left] >> i) & 1) == 1) { bitCounts[i]--; } } left++; } else { // Window's OR is too small, cannot shrink further break; } } } return minLength > n ? -1 : minLength; }}Complexity
Time
O(N * D), where N is the length of `nums` and D is the number of bits in the integers (approximately 31). Both `right` and `left` pointers traverse the array at most once. For each element added or removed, we perform a constant number of bit operations (D). Thus, the complexity is effectively linear, O(N).
Space
O(1), as the `bitCounts` array has a fixed size (31), which is independent of the input size N.
Trade-offs
Pros
Highly efficient with a time complexity that is effectively linear in the size of the input array.
Guaranteed to pass within the time limits for the given constraints.
Cons
The logic is more complex than the brute-force approach.
Requires careful handling of bit manipulation and window shrinking logic.
Solutions
Solution
class Solution {public int minimumSubarrayLength(int[] nums, int k) { int n = nums.length; int[] cnt = new int[32]; int ans = n + 1; for (int i = 0, j = 0, s = 0; j < n; ++j) { s |= nums[j]; for (int 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 (int h = 0; h < 32; ++h) { if ((nums[i] >> h & 1) == 1) { if (--cnt[h] == 0) { s ^= 1 << h; } } } } } return ans > n ? -1 : ans; }}class Solution {public: int minimumSubarrayLength(vector<int> &nums, int k) { int n = nums.size(); int cnt[32]{}; int ans = n + 1; for (int i = 0, j = 0, s = 0; j < n; ++j) { s |= nums[j]; for (int h = 0; h < 32; ++h) { if ((nums[j] >> h & 1) == 1) { ++cnt[h]; } } for (; s >= k && i <= j; ++i) { ans = min(ans, j - i + 1); for (int h = 0; h < 32; ++h) { if ((nums[i] >> h & 1) == 1) { if (--cnt[h] == 0) { s ^= 1 << h; } } } } } return ans > n ? -1 : ans; }};class Solution: def minimumSubarrayLength(self, nums: List[int], k: int) -> int: n = len(nums) cnt = [0] * 32 ans = n + 1 s = i = 0 for j, x in enumerate(nums): s |= x for h in range(32): if x >> h & 1: cnt[h] += 1 while s >= k and i <= j: ans = min(ans, j - i + 1) y = nums[i] for h in range(32): if y >> h & 1: cnt[h] -= 1 if cnt[h] == 0: s ^= 1 << h i += 1 return - 1 if ans > n else ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.