Shortest Subarray With OR at Least K I - Video Solutions

Problem Overview: You are given an integer array nums and a value k. The task is to find the length of the shortest non-empty subarray whose bitwise OR is greater than or equal to k. If no such subarray exists, return -1. The challenge comes from the behavior of the bitwise OR operation: once a bit becomes 1, it stays 1 when more elements are added.

Approach 1: Brute Force Enumeration (O(n² * 32) time, O(1) space)

Start every subarray from index i and expand the end pointer j one element at a time. Maintain a running OR value as you extend the subarray using current_or |= nums[j]. After each expansion, check whether current_or >= k. Once the condition is satisfied, update the minimum length and stop extending that start index because any longer subarray will only increase the length. The complexity becomes O(n²) in the worst case, with a constant factor related to bit operations (up to 32 bits for integers). This approach is simple and good for understanding how OR accumulates across a range.

Approach 2: Sliding Window with Bit Counters (O(n * 32) time, O(32) space)

The optimal solution uses a sliding window combined with bit manipulation. The window expands with a right pointer and shrinks with a left pointer. The key difficulty is that removing an element from a window does not directly undo the OR operation. To handle this, maintain an array of size 32 where each index counts how many numbers in the current window contribute that bit.

When you add a number, iterate through its bits and increment the corresponding counters. Reconstruct the current OR value by checking which bit counters are non-zero. If the OR becomes at least k, attempt to shrink the window from the left while maintaining the condition. When removing a number, decrement its bit counters and recompute the OR accordingly. Each element enters and leaves the window once, and each update processes up to 32 bits, resulting in O(n * 32) time and O(32) extra space.

This approach works well because the OR value only depends on whether at least one element contributes a bit. Tracking frequencies allows the window to both grow and shrink efficiently while preserving correctness.

Recommended for interviews: Start by explaining the brute force enumeration to demonstrate understanding of how bitwise OR accumulates across subarrays. Then move to the optimized sliding window solution. Interviewers typically expect the O(n * 32) approach because it combines array traversal, two pointers, and bit tracking to efficiently maintain the OR value while shrinking the window.