3097. Shortest Subarray With OR at Least K II

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 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 * 105


• 0 <= nums[i] <= 109


• 0 <= k <= 109

Hint:

1. For each nums[i], we can maintain each subarray’s bitwise OR result ending with it.


2. The property of bitwise OR is that it never unsets any bits and only sets new bits


3. 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:

1. 
   Sliding Window Approach: Iterate over the array using two pointers, maintaining a subarray whose OR value is checked.


2. 
   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.


3. 
   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:

1. Traverse the array, for each element, maintain a running OR.


2. For each element, check if the OR exceeds or equals k. If it does, try to shrink the window from the left side.


3. 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: a star on GitHub or sharing the post on your favorite social networks 😍.

1. 
   

   Subarray : A subarray is a contiguous non-empty sequence of elements within an array. ↩