3095. Shortest Subarray With OR at Least K I

Problem Statement

link: LeetCode.cn LeetCode 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:

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

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

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

Constraints: 1 <= nums.length <= 50 0 <= nums[i] <= 50 0 <= k < 64

Solution Approach

Use a sliding window to find the shortest subarray where the cumulative bitwise OR of elements meets or exceeds the given integer k.

Algorithm

1. Sliding Window Technique: Use a sliding window to efficiently explore different subarrays within the given array.
2. Bitwise OR Calculation: Continuously compute the bitwise OR for elements within the current window, expanding or shrinking the window as needed.
3. Check Minimum Length: Track and update the length of the shortest subarray where the bitwise OR meets or exceeds the integer k, returning the minimum found, or -1 if no such subarray exists.

Implement

    class Solution:
  def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
      ans = inf
      cur = dict()
      for i, x in enumerate(nums):
          cur = {_or | x: left for _or, left in cur.items()}
          cur[x] = i
          for _or, left in cur.items():
              if _or >= k:
                  ans = min(ans, i - left + 1)
      return ans if ans != inf else -1

    
    

Twitter  facebook  Email