Problem

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.

Examples

Example 1:

1
2
3
4

Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The subarray `[3]` has `OR` value of `3`. Hence, we return `1`.

Example 2:

1
2
3
4

Input: nums = [2,1,8], k = 10
Output: 3
Explanation:
The subarray `[2,1,8]` has `OR` value of `11`. Hence, we return `3`.

Example 3:

1
2
3
4

Input: nums = [1,2], k = 0
Output: 1
Explanation:
The subarray `[1]` has `OR` value of `1`. Hence, we return `1`.

Solution

Method 1 - Sliding Window

Using a strategy of managing the window elements, we can use two pointers to keep track of the current window.

To find the minimum length special subarray ending at index end, we consider our current window [0, end] (both inclusive) and calculate its bitwise OR based on a 32-bit array and a result num.

If num is less than k, we expand the window by including the next element nums[end + 1]. We continue this process until we find a special subarray where num is at least k. At this point, we have a candidate for the answer.

Next, we attempt to minimise the length by shrinking the window from the left side while maintaining the special condition num >= k.

Once shrinking the window causes the special condition to be false (num becomes less than k), we remember that the previous window [start', end'] was valid and found a possible answer end' - start' + 1.

Then, for finding the special subarray ending at index end' + 1, we start from start' + 1 instead of completely restarting. Since we have already found a possible answer of length end' - start' + 1, we only consider shorter lengths moving forward.

This technique leverages two pointers for an efficient sliding window approach.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int ans = n + 1;
        int[] bits = new int[32];
        
        for (int start = 0, end = 0; end < n; end++) {
            update(bits, nums[end], 1); // Insert nums[end] into the window
            while (start <= end && bitsToNum(bits) >= k) {
                ans = Math.min(ans, end - start + 1);
                update(bits, nums[start++], -1); // Remove nums[start] from the window
            }
        }
        
        return ans != n + 1 ? ans : -1;
    }
    
    private void update(int[] bits, int x, int change) {
        // Insert or remove an element from the window. Time complexity: O(32)
        for (int i = 0; i < 32; i++) {
            if (((x >> i) & 1) != 0) {
                bits[i] += change;
            }
        }
    }

    private int bitsToNum(int[] bits) {
        // Convert the 32-size bits array to an integer. Time complexity: O(32)
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if (bits[i] != 0) {
                res |= 1 << i;
            }
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def minimum_subarray_length(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = n + 1
        bits = [0] * 32

        def update(bits: List[int], x: int, change: int) -> None:
            # Insert or remove an element from the window. Time complexity: O(32)
            for i in range(32):
                if (x >> i) & 1 != 0:
                    bits[i] += change

        def bits_to_num(bits: List[int]) -> int:
            # Convert the 32-size bits array to an integer. Time complexity: O(32)
            res = 0
            for i in range(32):
                if bits[i] != 0:
                    res |= 1 << i
            return res

        start = 0
        for end in range(n):
            update(bits, nums[end], 1)  # Insert nums[end] into the window
            while start <= end and bits_to_num(bits) >= k:
                ans = min(ans, end - start + 1)
                update(bits, nums[start], -1)  # Remove nums[start] from the window
                start += 1

        return ans if ans != n + 1 else -1

Complexity

  • ⏰ Time complexity: O(n),
    • The primary loop runs from end = 0 to end = n-1, which is O(n).
    • The update(bits, nums[end], 1) and update(bits, nums[start], -1) each have a complexity of O(32) because the loop within update runs for a fixed number of 32 iterations (since we are dealing with 32-bit integers).
    • In the worst-case scenario, the start pointer can be incremented up to n times. Given that each increment includes a call to bits_to_num(bits), which runs in O(32), this can happen n times in total, leading to an additive term of O(32n).
  • 🧺 Space complexity: O(1)