Shortest Subarray With OR at Least K I
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible non-empty subarray. For each subarray, it computes the bitwise OR of its elements and compares it with k. The length of the shortest valid subarray is tracked and returned.
Algorithm
- Initialize
minLengthto a very large value (e.g.,Integer.MAX_VALUE). - Iterate through each possible starting index
ifrom0ton-1. - For each
i, iterate through each possible ending indexjfromiton-1. - For each subarray
nums[i..j], calculate its bitwise OR by iterating fromitoj. - If the calculated OR is greater than or equal to
k, updateminLength = min(minLength, j - i + 1). - After all loops complete, if
minLengthremains at its initial large value, return -1. Otherwise, returnminLength.
Walkthrough
The algorithm uses three nested loops. The outer two loops define the start (i) and end (j) indices of a subarray. The innermost loop then iterates from i to j to calculate the bitwise OR of the elements within that subarray. If this OR value is at least k, we update our answer with the current subarray's length if it's smaller than the minimum length found so far. After checking all subarrays, if no valid subarray was found, we return -1; otherwise, we return the minimum length.
class Solution { public int shortestSubarray(int[] nums, int k) { int n = nums.length; int minLength = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Subarray is nums[i..j] int currentOR = 0; for (int l = i; l <= j; l++) { currentOR |= nums[l]; } if (currentOR >= k) { minLength = Math.min(minLength, j - i + 1); } } } return minLength == Integer.MAX_VALUE ? -1 : minLength; }}Complexity
Time
O(n³), where `n` is the number of elements in `nums`. The three nested loops lead to a cubic time complexity, which can be slow for larger inputs but is acceptable for the given constraints.
Space
O(1), as we only use a constant amount of extra space for variables like `minLength` and `currentOR`.
Trade-offs
Pros
Very straightforward to conceptualize and implement.
Guaranteed to be correct as it checks every single possibility.
Cons
Highly inefficient due to its cubic time complexity.
Involves a lot of redundant computation, as the OR of a subarray is recalculated repeatedly.
This approach improves on the naive brute-force method by eliminating the innermost loop. It iterates through all subarrays, but calculates the bitwise OR incrementally. For a fixed starting point, as we extend the subarray to the right, the new OR is just the previous OR combined with the new element.
Algorithm
- Initialize
minLengthto a very large value (e.g.,Integer.MAX_VALUE). - Iterate through each possible starting index
ifrom0ton-1. - Initialize
currentOR = 0for the subarray starting ati. - For each
i, iterate through each possible ending indexjfromiton-1. - Update the OR value for the subarray
nums[i..j]:currentOR = currentOR | nums[j]. - If
currentOR >= k, updateminLength = min(minLength, j - i + 1). - After all loops complete, if
minLengthremains at its initial large value, return -1. Otherwise, returnminLength.
Walkthrough
We use two nested loops. The outer loop fixes the starting index i of the subarray. The inner loop iterates from i to the end of the array, defining the ending index j. A variable currentOR is used to keep track of the bitwise OR of the elements in the current subarray nums[i..j]. As j increments, currentOR is updated by OR-ing it with nums[j]. This avoids recalculating the OR from scratch. If at any point currentOR becomes greater than or equal to k, we update the minimum length found so far.
class Solution { public int shortestSubarray(int[] nums, int k) { int n = nums.length; int minLength = Integer.MAX_VALUE; 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); } } } return minLength == Integer.MAX_VALUE ? -1 : minLength; }}Complexity
Time
O(n²), where `n` is the number of elements in `nums`. The two nested loops result in a quadratic time complexity, which is efficient enough for the given constraints.
Space
O(1), as the extra space used does not depend on the input size.
Trade-offs
Pros
A significant improvement in efficiency over the O(n³) approach.
Simple to implement and understand.
Optimal for the given problem constraints.
Cons
May be too slow for problems with much larger constraints on
n.
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.