#3097

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Shortest Subarray With OR at Least K II

Find the length of the shortest subarray where the bitwise OR of all its elements is at least a given value.

Problem Statement

You are given an array nums of non-negative integers and an integer k. The task is to find the length of the shortest special subarray, where the bitwise OR of all elements is at least k. If no such subarray exists, return -1.

A subarray is considered special if the bitwise OR of its elements is greater than or equal to k. You need to return the length of the shortest such subarray or -1 if no valid subarray exists.

Examples

Example 1

Input: nums = [1,2,3], k = 2

Output: 1

The subarray [3] has OR value of 3 . Hence, we return 1 .

Example 2

Input: nums = [2,1,8], k = 10

Output: 3

The subarray [2,1,8] has OR value of 11 . Hence, we return 3 .

Example 3

Input: nums = [1,2], k = 0

Output: 1

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

Solution Approach

Sliding Window with Bitwise OR

To solve this problem efficiently, we use the sliding window technique where we maintain a running OR of the current subarray. By updating the OR value incrementally as the window expands, we avoid recalculating the OR from scratch for every subarray.

Efficient Window Shrinking

Once the OR of the subarray reaches or exceeds k, try to shrink the window from the left to minimize the length while maintaining the condition. This step helps ensure that we find the shortest subarray with the desired OR value.

Optimizing with Deque

Using a deque, we can keep track of the indices of the subarrays whose ORs are calculated. This helps quickly identify the smallest subarray with the required OR value.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because each element is processed at most twice, once when expanding the window and once when shrinking. The space complexity is O(1) as we only need a constant amount of extra space for the window's OR and the deque used to track indices.

What Interviewers Usually Probe

Look for familiarity with sliding window and bitwise manipulation techniques.
Assess the ability to optimize a brute-force approach into an efficient solution.
Check for understanding of deque usage in maintaining a sliding window of indices.

Common Pitfalls or Variants

Common pitfalls

Not updating the OR value incrementally and recalculating it for each subarray.
Failing to shrink the window when the OR value meets or exceeds k.
Incorrectly handling edge cases, such as when no valid subarray exists.

Follow-up variants

What if the problem asked for the longest subarray instead of the shortest?
What if the array contains negative numbers, how would the solution change?
How would you handle a case where multiple subarrays have the same shortest length but different OR values?

FAQ

What is the pattern used to solve the Shortest Subarray With OR at Least K II problem?

The solution relies on the sliding window approach with a running OR value and the use of a deque to track the window efficiently.

How do I optimize the brute-force approach to solve this problem?

By using a sliding window and maintaining the OR value incrementally, you can avoid recalculating the OR for every subarray, making the approach more efficient.

What is the time complexity of the solution?

The time complexity is O(n) since each element is processed at most twice: once when expanding the window and once when shrinking it.

What happens if no special subarray exists?

If no subarray's OR meets or exceeds the given value k, the correct output is -1.

How does the deque help in solving the problem?

The deque is used to maintain indices of the subarrays efficiently, ensuring that we can shrink the window and check the minimum length of subarrays with the required OR value.

terminal

Solution

Solution 1: Two Pointers + Counting

We can observe that if we fix the left endpoint of the subarray, as the right endpoint moves to the right, the bitwise OR value of the subarray will only increase, not decrease. Therefore, we can use the double pointers method to maintain a subarray that meets the conditions.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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 ans

Continue Practicing

#3095 shortest subarray with or at least k i #3191 minimum operations to make binary array elements equal to one i #2935 maximum strong pair xor ii