We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Subarray With OR at Least K II

Difficulty: Medium

Problem Description

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.

Key Insights

  • The subarray's bitwise OR can only increase as more elements are added.
  • A single element can be a valid subarray if it is greater than or equal to k.
  • A sliding window approach helps efficiently find the shortest subarray with the required OR value.
  • We can use a deque to maintain the starting points of subarrays to quickly check their lengths when a valid OR is found.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will utilize a sliding window approach combined with a deque to maintain the starting indices of potential subarrays. The key steps are:

  1. Initialize a variable to keep track of the current OR value of the subarray.
  2. Use two pointers to represent the start and end of the subarray.
  3. Expand the end pointer to include more elements in the subarray and update the OR value.
  4. When the OR value meets or exceeds k, check the length of the current subarray and update the minimum length found.
  5. Move the start pointer to try to minimize the length while maintaining the OR condition.
  6. If no valid subarray is found, return -1.

Code Solutions

def shortestSubarrayWithOR(nums, k):
    from collections import deque
    
    n = len(nums)
    min_length = float('inf')
    current_or = 0
    start = 0
    queue = deque()

    for end in range(n):
        current_or |= nums[end]
        queue.append(end)

        while queue and current_or >= k:
            min_length = min(min_length, end - queue.popleft() + 1)
            if queue:
                current_or = 0
                for index in queue:
                    current_or |= nums[index]

    return min_length if min_length != float('inf') else -1
← Back to All Questions