Shortest Subarray With OR at Least K II

XXX. Minimum Subarray Length with Bitwise Operations

Array

Sliding Window

Bit Manipulation

Problem Statement:

Given an array of integers nums and an integer k, find the minimum length of a subarray where the bitwise OR of its elements is greater than or equal to k. Return -1 if no such subarray exists.

• Must maintain bitwise state of current window
• Need to track individual bit positions (0-31)
• Return minimum length subarray that satisfies condition

Algorithm:

1. **Bit Tracking**:
   • Use array to count set bits at each position
   • Update counts when adding/removing numbers
   • Convert bit counts back to number for comparison
2. **Sliding Window**:
   • Expand window by adding elements
   • Shrink window when condition is met
   • Track minimum window size that satisfies condition
3. **Helper Functions**:
   • update(): Modify bit counts for window changes
   • bitsToNum(): Convert bit counts to integer

Complexity:

Time Complexity: O(n * 32), where n is array length
Space Complexity: O(1), fixed size bit array

Implementation:

Java Solution:

class Solution {
    private void update(int[] bits, int x, int change) {
        for (int i = 0; i < 32; i++)                    // Update each bit position
            if (((x >> i) & 1) != 0) bits[i] += change;
    }
    
    private int bitsToNum(int[] bits) {
        int result = 0;
        for (int i = 0; i < 32; i++)                    // Convert bits to number
            if (bits[i] != 0) result |= 1 << i;
        return result;
    }
    
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length, result = n + 1;
        int[] bits = new int[32];
        for (int start = 0, end = 0; end < n; end++) {
            update(bits, nums[end], 1);                 // Add number to window
            
            while (start <= end && bitsToNum(bits) >= k) {
                result = Math.min(result, end - start + 1);
                update(bits, nums[start++], -1);        // Remove from window
            }
        }
        return result != n + 1 ? result : -1;
    }
}
                

Python Solution:

class Solution:
    def update(self, bits: List[int], x: int, change: int) -> None:
        for i in range(32):                            # Update each bit position
            if (x >> i) & 1: bits[i] += change
    
    def bits_to_num(self, bits: List[int]) -> int:
        result = 0
        for i in range(32):                            # Convert bits to number
            if bits[i]: result |= 1 << i
        return result
    
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        result = n + 1
        bits = [0] * 32
        start = 0
        
        for end in range(n):
            self.update(bits, nums[end], 1)            # Add number to window
            
            while start <= end and self.bits_to_num(bits) >= k:
                result = min(result, end - start + 1)
                self.update(bits, nums[start], -1)     # Remove from window
                start += 1
        
        return result if result != n + 1 else -1
                

C++ Solution:

class Solution {
private:
    void update(vector& bits, int x, int change) {
        for (int i = 0; i < 32; i++)                   // Update each bit position
            if ((x >> i) & 1) bits[i] += change;
    }
    
    int bitsToNum(vector& bits) {
        int result = 0;
        for (int i = 0; i < 32; i++)                   // Convert bits to number
            if (bits[i]) result |= 1 << i;
        return result;
    }
    
public:
    int minimumSubarrayLength(vector& nums, int k) {
        int n = nums.size(), result = n + 1;
        vector bits(32, 0);
        
        for (int start = 0, end = 0; end < n; end++) {
            update(bits, nums[end], 1);                // Add number to window
            
            while (start <= end && bitsToNum(bits) >= k) {
                result = min(result, end - start + 1);
                update(bits, nums[start++], -1);       // Remove from window
            }
        }
        return result != n + 1 ? result : -1;
    }
};
                

Explanation:

• **Bit Array Management**:
  • bits[i] tracks count of set bits at position i
  • Positive change (1) adds to window
  • Negative change (-1) removes from window
• **Window Operations**:
  • Expand window until OR condition is met
  • Shrink window to find minimum length
  • Track minimum valid window size
• **Bit Manipulation**:
  • Use right shift to check each bit position
  • Use OR operations to combine bits
  • Handle all 32 bits for complete number representation