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.
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 ; } }Video 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.