LeetCode 3095 - Shortest Subarray With OR at Least K I

The problem asks us to find the shortest subarray within a given array nums such that the bitwise OR of all elements in that subarray is at least k. A subarray is any contiguous sequence of elements in nums.

leetcodeeasyarraybit-manipulationsliding-window

LeetCode Problem 3095

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation, Sliding Window

Solution

Problem Understanding

The problem asks us to find the shortest subarray within a given array nums such that the bitwise OR of all elements in that subarray is at least k. A subarray is any contiguous sequence of elements in nums. The input array consists of non-negative integers, and the integer k is in the range [0, 63]. The output should be the length of this shortest subarray, or -1 if no such subarray exists.

In other words, for each possible subarray of nums, we compute the bitwise OR of its elements. Among all subarrays whose OR is >= k, we find the one with the minimum length. If none exists, the answer is -1.

The constraints tell us that the array length is small (1 <= nums.length <= 50), which permits approaches that examine many subarrays. The numbers themselves are small (0 <= nums[i] <= 50), so OR operations are cheap and bounded. Edge cases include k = 0, where any non-empty subarray satisfies the condition, arrays containing all zeros, or arrays where only the combination of all elements reaches k.

Approaches

The brute-force approach would examine all possible subarrays of nums, compute the bitwise OR for each, and track the minimum length of those satisfying OR >= k. This is correct because it checks every possible subarray, but the number of subarrays is O(n^2) and computing the OR for each takes O(n) in the naive implementation, resulting in O(n^3) time complexity, which is overkill even for n = 50.

The optimal approach leverages two observations. First, the bitwise OR operation is monotonic: adding elements to a subarray cannot decrease the OR. This allows a sliding window / two-pointer strategy. We expand a window from the left and right, maintaining the cumulative OR. When the OR reaches at least k, we try to shrink the window from the left while keeping OR >= k to find the minimal length. This reduces redundant OR computations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Compute OR for every possible subarray
Sliding Window / Two-Pointer O(n^2) O(1) Expand right pointer, shrink left to minimize length

Even though the two-pointer method is O(n^2), it is acceptable given the small constraint n <= 50.

Algorithm Walkthrough

  1. Initialize min_length to a value larger than the array length (e.g., len(nums) + 1) to track the shortest valid subarray found.
  2. Iterate over each possible starting index i of a subarray.
  3. Initialize a variable current_or to 0.
  4. For each end index j >= i, update current_or |= nums[j].
  5. If current_or >= k, compute the length j - i + 1. Update min_length if this length is smaller. Break the inner loop because any longer subarray starting at i will only increase the length.
  6. After checking all starting indices, return min_length if it was updated, otherwise return -1.

Why it works: The OR operation is monotonic; as we extend the subarray, the OR cannot decrease. Therefore, the first moment we reach >= k for a given start index i, we have the shortest subarray starting at i that satisfies the condition. Checking all starting indices ensures we find the global minimum.

Python Solution

from typing import List

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        min_length = 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_length = min(min_length, j - i + 1)
                    break
        
        return min_length if min_length <= n else -1

Explanation: We iterate over all possible subarray start indices i. For each start, we extend to the right while maintaining the cumulative OR. Once OR reaches k, we update the minimal length and break, because adding more elements would only increase the length. Finally, we check if min_length was updated, returning -1 if no valid subarray exists.

Go Solution

func minimumSubarrayLength(nums []int, k int) int {
    n := len(nums)
    minLength := n + 1
    
    for i := 0; i < n; i++ {
        currentOr := 0
        for j := i; j < n; j++ {
            currentOr |= nums[j]
            if currentOr >= k {
                if j - i + 1 < minLength {
                    minLength = j - i + 1
                }
                break
            }
        }
    }
    
    if minLength <= n {
        return minLength
    }
    return -1
}

Go-specific notes: The logic mirrors the Python version. We avoid slices or extra memory, just maintaining simple integers. No special handling is needed for empty slices since nums length is guaranteed >=1. Go requires explicit bounds checking, which is naturally handled by the for loops.

Worked Examples

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

i j current_or min_length
0 0 1 -
0 1 3 2
0 2 3 2
1 1 2 1
2 2 3 1

Output: 1

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

i j current_or min_length
0 0 2 -
0 1 3 -
0 2 11 3
1 1 1 3
1 2 9 3
2 2 8 3

Output: 3

Example 3: nums = [1,2], k = 0

i j current_or min_length
0 0 1 1

Output: 1

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Nested loops over start and end indices. Each OR is O(1) due to small integer values.
Space O(1) Only a few integer variables are used, no extra data structures.

The small input size allows the quadratic solution to run efficiently.

Test Cases

# Basic examples
assert Solution().minimumSubarrayLength([1,2,3], 2) == 1  # minimal single element
assert Solution().minimumSubarrayLength([2,1,8], 10) == 3  # needs all elements
assert Solution().minimumSubarrayLength([1,2], 0) == 1  # k = 0

# Edge cases
assert Solution().minimumSubarrayLength([0,0,0], 1) == -1  # no valid subarray
assert Solution().minimumSubarrayLength([50]*50, 50) == 1  # first element suffices
assert Solution().minimumSubarrayLength([1,2,4,8,16], 31) == 5  # all needed

# Smallest input
assert Solution().minimumSubarrayLength([0], 0) == 1  # single element satisfies k = 0
assert Solution().minimumSubarrayLength([0], 1) == -1  # single zero element cannot reach k

# Mixed values
assert Solution().minimumSubarrayLength([1,3,5,7], 7) == 3  # subarray [3,5,7]
Test Why
[1,2,3], k=2 Minimal subarray satisfies OR
[2,1,8], k=10 Entire array needed to satisfy OR
[1,2], k=0 Any element satisfies k=0
[0,0,0], k=1 No subarray can reach k
[50]*50, k=50 First element suffices, tests large repeated elements
[1,2,4,8,16], k=31 All elements required to reach k
[0], k=0 Single-element edge case
[0], k=1 Single-element cannot reach k
[1,3,5,7], k=7 Requires middle subarray