3097. Shortest Subarray With OR at Least K II

Intuition

To solve this problem, we need a way to track the bitwise OR value of subarrays efficiently as we slide through the array. The BitOrQueue class is designed to maintain the bitwise OR of a dynamic window of elements, supporting push and pop operations. This allows us to check the OR of subarrays as they grow and shrink dynamically. Using a sliding window approach, we can find the shortest subarray where the OR is at least k.

Approach 1: Sliding Window with Bit-Or Queue

The solution employs a custom data structure, BitOrQueue, which keeps track of the bitwise OR value for a sliding window. This queue also maintains a frequency count of set bits at each bit position to allow adding or removing elements from the OR efficiently. We then apply a sliding window technique, expanding the window until the OR is at least k, then shrinking from the left to find the shortest valid subarray.

Explanation:

1. Class BitOrQueue:
2. The BitOrQueue class provides a structure to handle dynamic OR operations in a window.
3. It uses an array freq to count the occurrences of each bit position across elements in the window, allowing efficient push and pop operations for the OR calculation.
4. push operation:
   • Adds an element x to the queue.
   • Updates the bitwise OR val by OR-ing it with x.
   • Updates the frequency of each bit position based on the bits set in x.
5. pop operation:
   • Removes an element x from the queue.
   • Decrements the frequency of each bit position based on the bits in x.
   • Updates the OR value val by clearing bits with frequency zero.
6. Function minimumSubarrayLength:
7. Initialization:
   • Resets the BitOrQueue to clear any previous OR values.
   • Initializes res with -1 (to represent no valid subarray found) and left to represent the start of the sliding window.
8. Sliding Window Execution:
   • Expands the window by pushing nums[right] to BitOrQueue.
   • Checks if the OR value in BitOrQueue meets or exceeds k.
   • If it does, it updates the minimum length res and contracts the window from the left by popping nums[left].
9. Return Result:
   • After examining all subarrays, res contains the length of the shortest subarray with OR at least k, or -1 if none exists.

Complexity

• Time complexity: O(n), where n is the size of nums.
• Space complexity: O(1)

Code

template <class T>
class BitOrQueue {
private:
    static const int n = sizeof(T) * 8;
    size_t freq[n];

public:
    T val;

    void push(const T& x) {
        val |= x;
        for (int i = 0; i < n; i++) {
            freq[i] += (x >> i) & 1;
        }
    }

    void pop(const T& x) {
        for (int i = 0; i < n; i++) {
            freq[i] -= x >> i & 1;
            val &= ~(!freq[i] << i);
        }
    }

    void reset() {
        val = 0;
        memset(freq, 0, sizeof(freq));
    }
};

BitOrQueue<int> bq;

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        if (k == 0) return 1;

        bq.reset();
        uint res = -1, left = 0;

        for (uint right = 0; right < nums.size(); right++) {
            bq.push(nums[right]);

            while (bq.val >= k) {
                res = min(res, right - left + 1);
                bq.pop(nums[left++]);
            }
        }

        return res;
    }
};

Code - Java

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int l = 0, r = 0;
        int minLen = Integer.MAX_VALUE;
        int or = 0;
        int[] bits = new int[32];

        if (k == 0) {
            return 1;
        }

        while (r < n) {
            or |= nums[r];
            add(bits, nums[r]);

            while (or >= k) {
                minLen = Math.min(minLen, r - l + 1);
                or = remove(bits, nums[l]);
                l++;
            }

            r++;
        }

        return minLen != Integer.MAX_VALUE ? minLen : -1;
    }

    public int remove(int[] arr, int n) {
        int i = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                arr[i]--;
            }
            n >>= 1;
            i++;
        }

        int decimal = 0;
        for (i = 0; i < 32; i++) {
            if (arr[i] > 0) {
                decimal += (1 << i);
            }
        }
        return decimal;
    }

    public void add(int[] arr, int n) {
        int i = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                arr[i]++;
            }
            n >>= 1;
            i++;
        }
    }
}