Shortest Subarray With OR at Least K II - Video Solutions

Problem Overview: You are given an integer array nums and an integer k. The task is to find the length of the shortest contiguous subarray whose bitwise OR is at least k. If no such subarray exists, return -1. The challenge comes from maintaining the OR value efficiently while shrinking or expanding the window.

Approach 1: Brute Force Method (Time: O(n^2 * 32), Space: O(1))

The simplest idea is to start a subarray at every index and extend it to the right while maintaining the running OR. For each starting position i, iterate j from i to n-1 and update current_or |= nums[j]. As soon as the OR becomes greater than or equal to k, record the length j - i + 1. Continue this process for every starting index and keep track of the minimum length found. This approach directly explores all subarrays, which leads to quadratic growth in the number of checks. Since integers have up to 32 bits, the OR operation itself is constant time, making the total complexity roughly O(n^2 * 32). This method is useful for validating logic or small input sizes but becomes too slow for large arrays.

Approach 2: Sliding Window with Bit Counting (Time: O(n * 32), Space: O(32))

A more efficient solution uses the sliding window technique combined with bit tracking. The window expands using a right pointer and contracts using a left pointer. The key challenge is that removing an element from a window does not easily update the OR value. To handle this, maintain a frequency array for each bit position (0–31). When a new element enters the window, iterate through its bits and increment the corresponding counters. When an element leaves the window, decrement the counters for the bits it contributed.

At any moment, reconstruct the current OR by checking which bit counters are greater than zero. If the OR becomes at least k, attempt to shrink the window from the left while maintaining the condition. Each element enters and leaves the window at most once, and each update touches at most 32 bits. This results in O(n * 32) time and constant auxiliary space. The method combines ideas from array traversal and bit manipulation to maintain the OR dynamically.

Recommended for interviews: Start by explaining the brute force approach to demonstrate understanding of the subarray search space. Then move to the sliding window optimization. Interviewers expect the optimized version because it handles the difficulty of removing OR contributions using bit counters. This shows you understand both two-pointer window management and bit-level state tracking.