• Leetcode POTDs

Problem 3097 Shortest Subarray With OR at Least K II

Problem Statement

Link - Problem 3097

Question

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 1:

Example 2:

Example 3:

Constraints:

• 1 <= nums.length <= 2 * 105
• 0 <= nums[i] <= 109
• 0 <= k <= 109

Solution

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        vector<int> bit_count(32, 0);
        int current_val = 0;
        int start = 0, end = 0, min_length = INT_MAX;

        while (end < nums.size()) {
            update_bits(bit_count, current_val, nums[end], 1);

            while (start <= end && current_val >= k) {
                min_length = min(min_length, end - start + 1);
                update_bits(bit_count, current_val, nums[start], -1);
                start++;
            }

            end++;
        }

        return min_length == INT_MAX ? -1 : min_length;
    }

private:
    void update_bits(vector<int>& bit_count, int& current_val, int num, int val) {
        for (int i = 0; i < 32; i++) {
            if (num & (1 << i)) {
                bit_count[i] += val;

                // Update current_val based on the change in bit count
                if (bit_count[i] == 1 && val == 1) {
                    current_val |= (1 << i);  // Set the bit if it's newly active
                }
                else if (bit_count[i] == 0 && val == -1) {
                    current_val &= ~(1 << i); // Clear the bit if it's no longer active
                }
            }
        }
    }
};

Complexity Analysis

| Algorithm                        | Time Complexity | Space Complexity |
| -------------------------------- | --------------- | ---------------- |
| Sliding window with two-pointers | O(n)            | O(1)             |

Explanation

1. Intuition

• The problem requires finding the shortest subarray with a bitwise OR of at least k.
• A sliding window approach can be used to efficiently find the shortest subarray.
• The sliding window should expand to the right until the bitwise OR is at least k.
• Once the bitwise OR is at least k, the window can start contracting from the left.
• The contraction should stop when the bitwise OR is less than k, and the window should expand again.
• This process continues until the entire array has been traversed.
• The minimum length of the subarray with a bitwise OR of at least k is the answer.

2. Implementation

• A vector bit_count of size 32 is used to keep track of the bit counts of the current window.
• The update_bits function is used to update the bit_count and current_val based on the addition or removal of a number.
• The while loop is used to expand the window to the right until the bitwise OR is at least k.
• The while loop inside the outer loop is used to contract the window from the left until the bitwise OR is less than k.
• The minimum length of the subarray is updated whenever a valid subarray is found.
• The update_bits function uses bitwise operations to update the bit_count and current_val.
• The current_val is updated based on the change in the bit count, and the bit_count is updated based on the addition or removal of a number.

Complexity Analysis

Time Complexity:

• The time complexity is determined by the two nested loops: the outer while loop that traverses the input array (while (end < nums.size())), and the inner while loop that slides the window when the bit sum exceeds the target (while (start <= end && current_val >= k)).
• The dominant operation is the update of the bit count array in the update_bits function, which runs in linear time with respect to the bit length (32 bits). However, since the bit length is a constant, this operation is considered O(1) per iteration.
• Given that the input array is traversed only once, and the inner while loop only contributes linearly to the overall time complexity due to the sliding window approach, the overall time complexity is O(n) where n is the length of the input array.

Space Complexity:

• The space complexity is primarily determined by the fixed-size bit count array (vector<int> bit_count(32, 0)).
• Although a dynamic array is used to represent the bit count, its maximum size is capped at 32, making the space complexity constant with respect to the input size.
• The space used by the input array and the sliding window pointers do not contribute to the space complexity since they are part of the input and are not allocated by the algorithm.

Footnote

This question is rated as Medium difficulty.

Hints

For each nums[i], we can maintain each subarray’s bitwise OR result ending with it.

The property of bitwise OR is that it never unsets any bits and only sets new bits

So the number of different results for each nums[i] is at most the number of bits 32.

Similar Questions: