Shortest Subarray With OR at Least K I

Difficulty: Easy | Acceptance: 44.50% | Paid: No Topics: Array, Bit Manipulation, Sliding Window

You are given an array nums of non-negative integers and an integer k.

Return the length of the shortest non-empty subarray of nums whose bitwise OR is at least k.

If there is no such subarray, return -1.

• Examples
• Constraints
• Brute Force
• Sliding Window

Examples

Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The subarray [2] has OR value 2 which is >= k.
The subarray [3] has OR value 3 which is >= k.
The shortest length is 1.

Input: nums = [2,1,8], k = 10
Output: 2
Explanation:
The subarray [2,8] has OR value 10 which is >= k.
The subarray [1,8] has OR value 9 which is < k.
The subarray [2,1,8] has OR value 11 which is >= k.
The shortest length is 2.

Input: nums = [1,2], k = 0
Output: 1
Explanation:
Since k is 0, any single element subarray satisfies the condition.
The shortest length is 1.

Constraints

1 <= nums.length <= 50
1 <= nums[i] <= 50
0 <= k <= 10⁶

Brute Force

Intuition Since the array size is very small (n <= 50), we can afford to check every possible subarray. We iterate through all starting points and extend the subarray to the right, calculating the bitwise OR incrementally.

Steps

• Initialize min_len to a value larger than the array size (e.g., n + 1).
• Iterate i from 0 to n - 1 as the start of the subarray.
• Initialize current_or to 0.
• Iterate j from i to n - 1 as the end of the subarray.
• Update current_or by performing bitwise OR with nums[j].
• If current_or >= k, update min_len with j - i + 1 and break the inner loop (since extending further will only increase the length).
• After loops, if min_len was updated, return it; otherwise, return -1.

class Solution:
    def minimumSubarrayLength(self, nums: list[int], k: int) -> int:
        n = len(nums)
        min_len = n + 1
        for i in range(n):
            current_or = 0
            for j in range(i, n):
                current_or |= nums[j]
                if current_or >= k:
                    min_len = min(min_len, j - i + 1)
                    break
        return -1 if min_len == n + 1 else min_len

Complexity

• Time: O(n²) - We check every subarray starting at every index.
• Space: O(1) - We only use a few variables for tracking.
• Notes: Simple to implement and very efficient for the given constraints (n <= 50).

Sliding Window

Intuition Bitwise OR is a monotonic operation: adding more elements to a subarray can only maintain or increase the OR value. This property allows us to use a sliding window approach. We maintain a window [left, right] and try to shrink it from the left while the condition is met to find the minimum length. To efficiently remove elements from the OR calculation, we maintain a count of set bits at each position.

Steps

• Initialize left = 0, min_len = n + 1, and an array bit_counts of size 32 (to cover 32-bit integers) initialized to 0.
• Iterate right from 0 to n - 1:
  • Add nums[right] to the window by updating bit_counts and the current OR value.
  • While the current OR is >= k and left <= right:
    • Update min_len with right - left + 1.
    • Remove nums[left] from the window by decrementing bit_counts. If a bit count drops to 0, clear that bit in the current OR.
    • Increment left.
• Return min_len if updated, otherwise -1.

class Solution:
    def minimumSubarrayLength(self, nums: list[int], k: int) -> int:
        n = len(nums)
        min_len = n + 1
        left = 0
        current_or = 0
        bit_counts = [0] * 32
        
        for right in range(n):
            # Add nums[right] to the window
            for i in range(32):
                if nums[right] & (1 << i):
                    bit_counts[i] += 1
                    if bit_counts[i] == 1:
                        current_or |= (1 << i)
            
            # Shrink window while condition is met
            while current_or >= k and left <= right:
                min_len = min(min_len, right - left + 1)
                
                # Remove nums[left] from the window
                for i in range(32):
                    if nums[left] & (1 << i):
                        bit_counts[i] -= 1
                        if bit_counts[i] == 0:
                            current_or &= ~(1 << i)
                left += 1
                
        return -1 if min_len == n + 1 else min_len

Complexity

• Time: O(n * 32) = O(n) - We process each element at most twice (once when added, once when removed), and each processing involves 32 bit operations.
• Space: O(1) - The bit_counts array is of fixed size 32.
• Notes: More complex to implement than brute force but optimal for larger input sizes.