3097. Shortest Subarray With OR at Least K II
Difficulty: Medium
Topics: Array
, Bit Manipulation
, Sliding Window
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 subarray1 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]
hasOR
value of3
. Hence, we return1
.
Example 2:
- Input: nums = [2,1,8], k = 10
- Output: 3
-
Explanation: The subarray
[2,1,8]
hasOR
value of11
. Hence, we return3
.
Example 3:
- Input: nums = [1,2], k = 0
- Output: 1
-
Explanation: The subarray
[1]
hasOR
value of1
. Hence, we return1
.
Constraints:
1 <= nums.length <= 2 * 105
0 <= nums[i] <= 109
0 <= k <= 109
Hint:
- For each
nums[i]
, we can maintain each subarray’s bitwiseOR
result ending with it. - The property of bitwise
OR
is that it never unsets any bits and only sets new bits - So the number of different results for each
nums[i]
is at most the number of bits 32.
Solution:
We can use a sliding window approach combined with bit manipulation to keep track of the OR of elements in the window.
Plan:
- Sliding Window Approach: Iterate over the array using two pointers, maintaining a subarray whose OR value is checked.
-
Bitwise OR: The OR operation accumulates values. It never reduces the result (i.e., once a bit is set to
1
, it cannot be unset). This means as we extend the window, the OR value only increases or stays the same. - Efficiency: We can use a deque (double-ended queue) to maintain indices of the subarrays. This allows us to efficiently slide the window while keeping track of the minimum subarray length.
Steps:
- Traverse the array, for each element, maintain a running OR.
- For each element, check if the OR exceeds or equals
k
. If it does, try to shrink the window from the left side. - The sliding window should be moved efficiently by keeping track of the OR value in a deque structure to allow constant time sliding and shrinking.
Let's implement this solution in PHP: 3097. Shortest Subarray With OR at Least K II
<?php
class Solution {
const K_MAX_BIT = 30; // Maximum bit position we will check
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function minimumSubarrayLength($nums, $k) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* @param $ors
* @param $num
* @param $count
* @return int
*/
private function orNum($ors, $num, &$count) {
// Update the ors value and count bits that are set
...
...
...
/**
* go to ./solution.php
*/
}
/**
* @param $ors
* @param $num
* @param $count
* @return int
*/
private function undoOrNum($ors, $num, &$count) {
// Reverse the update on ors and count bits that are reset
...
...
...
/**
* go to ./solution.php
*/
}
}
// Example usage
$solution = new Solution();
$nums1 = [1, 2, 3];
$k1 = 2;
echo $solution->minimumSubarrayLength($nums1, $k1) . "\n"; // Output: 1
$nums2 = [2, 1, 8];
$k2 = 10;
echo $solution->minimumSubarrayLength($nums2, $k2) . "\n"; // Output: 3
$nums3 = [1, 2];
$k3 = 0;
echo $solution->minimumSubarrayLength($nums3, $k3) . "\n"; // Output: 1
?>
Explanation:
-
minimumSubarrayLength
Method:- Initialize
ans
to an impossible high value ($n + 1
). - Use two pointers
l
(left) andr
(right) to expand and shrink the window. - Calculate the OR of the subarray as you expand the window with
orNum
and reduce it withundoOrNum
when shrinking. - Whenever the OR result meets or exceeds
k
, check if the current window size is smaller thanans
.
- Initialize
-
orNum
andundoOrNum
Methods:-
orNum
method: Adds bits to the cumulative OR by updating thecount
array. If a bit is newly set in the window (meaningcount[i]
becomes1
), that bit is added toors
. -
undoOrNum
method: Removes bits from the cumulative OR when sliding the window leftward. If a bit is no longer set in any of the numbers in the window (meaningcount[i]
becomes0
), that bit is removed fromors
.
-
-
Time Complexity:
- The time complexity is O(n) because each index is added and removed from the deque at most once.
-
n
is the length of the input array.
4*Time Complexity*:
- The space complexity is O(n) for storing the prefix OR array and the deque.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
-
Subarray : A subarray is a contiguous non-empty sequence of elements within an array. ↩
Top comments (0)