#3095

Easy

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Shortest Subarray With OR at Least K I

Find the shortest non-empty subarray in nums whose bitwise OR reaches at least k using sliding window efficiently.

Problem Statement

Given an array of non-negative integers nums and an integer k, identify subarrays whose bitwise OR of all elements reaches at least k. Return the length of the shortest such non-empty subarray or -1 if none exists.

A subarray is defined as a contiguous portion of nums. The bitwise OR accumulates all elements in the subarray, and the goal is to minimize its length while ensuring the OR is at least k.

Examples

Example 1

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

Output: 1

The subarray [3] has OR value of 3 . Hence, we return 1 . Note that [2] is also a special subarray.

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 <= 50
0 <= nums[i] <= 50
0 <= k < 64

Solution Approach

Sliding Window with Bitwise OR

Maintain a window [left, right] and a running OR value. Expand right while OR < k, then attempt to contract left to minimize length without dropping below k.

Brute Force for Small Arrays

Because nums.length <= 50, iterate all subarrays computing their OR to find the minimal length. This handles edge cases and validates sliding window results.

Optimize with Early Stopping

If a single element nums[i] >= k, return 1 immediately. Stop extending the window once OR >= k and update minimal length, reducing unnecessary computation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity can range from O(n^2) for brute force to O(n) for sliding window if OR updates are efficient. Space is O(1) if OR is tracked inline, or O(n) if storing prefix OR values.

What Interviewers Usually Probe

Consider that small constraints allow simple brute force to verify correctness.
The problem favors bit manipulation combined with a sliding window pattern.
Expect follow-ups on optimizing OR computations and minimizing window length.

Common Pitfalls or Variants

Common pitfalls

Not updating the minimal length after contracting the window.
Assuming all subarrays must be longer than 1 instead of checking single elements.
Failing to correctly compute OR when elements are added or removed from the window.

Follow-up variants

Find the longest subarray with OR less than k.
Return all shortest subarrays with OR at least k.
Modify nums with insertions to guarantee a special subarray exists.

FAQ

What is the easiest way to start solving Shortest Subarray With OR at Least K I?

Start by checking single elements against k, then expand using a sliding window to track OR and minimize length.

Can brute force work for this problem?

Yes, because nums.length <= 50, checking all subarrays is feasible and helps verify sliding window correctness.

How does bitwise OR affect the sliding window approach?

The OR only increases when adding elements, so contracting the window carefully maintains correctness while minimizing length.

What if no subarray reaches OR >= k?

Return -1, since no special subarray exists according to the problem definition.

Are there edge cases to consider in this sliding window pattern?

Yes, single-element subarrays, zeros in nums, and OR values exactly equal to k require careful handling.

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

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