Shortest Subarray With OR at Least K II - Solution & Explanation
Problem Statement
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:
Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The subarray [3] has OR value of 3. Hence, we return 1.
Example 2:
Input: nums = [2,1,8], k = 10
Output: 3
Explanation:
The subarray [2,1,8] has OR value of 11. Hence, we return 3.
Example 3:
Input: nums = [1,2], k = 0
Output: 1
Explanation:
The subarray [1] has OR value of 1. Hence, we return 1.
Constraints:
1 <= nums.length <= 2 * 1050 <= nums[i] <= 1090 <= k <= 109
Approach Overview
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.
Approach 1: Sliding Window Technique
The sliding window approach allows us to efficiently consider subarrays by expanding and contracting the window size while checking the OR condition. We start by iterating over the array using two pointers that track the start and end of the current window. The objective is to maintain a OR condition that satisfies the requirement of being at least k, while minimizing the window size.
This C program uses two pointers left and right to define the window. We apply the OR operation to expand the window and check if the result meets or exceeds k. Simultaneously, we update the minimum length while shifting the left pointer to contract the window when possible.
Complexity
Time Complexity: O(n), as each element is processed at most twice.
Space Complexity: O(1), since no additional data structures proportional to input size are used.
Approach 2: Brute Force Method
The brute force approach involves examining all possible non-empty subarrays. Although this method is not efficient for large inputs, it is a straightforward solution that guarantees finding the result by evaluating each subarray's OR value and checking against the condition.
This brute force C implementation explores feasible subarrays starting from each index. For each starting point, it evaluates the OR running total for the current subarray until the OR exceeds or equals k.
Complexity
Time Complexity: O(n^2), as it checks each subarray.
Space Complexity: O(1), with basic indexing variables used.
Approach 3: Two Pointers + Counting
We can observe that if we fix the left endpoint of the subarray, as the right endpoint moves to the right, the bitwise OR value of the subarray will only increase, not decrease. Therefore, we can use the double pointers method to maintain a subarray that meets the conditions.
Specifically, we use two pointers i and j to represent the left and right endpoints of the subarray, respectively. Initially, both pointers are at the first element of the array. We use a variable s to represent the bitwise OR value of the subarray, and initially, the value of s is 0. We also need to maintain an array cnt of length 32, which represents the occurrence times of each bit in the binary representation of each element in the subarray.
In each step, we move j to the right by one position, and update s and cnt. If the value of s is greater than or equal to k, we continuously update the minimum length of the subarray and move i to the right by one position until the value of s is less than k. In this process, we also need to update s and cnt.
Finally, we return the minimum length. If there is no subarray that meets the conditions, we return -1.
The time complexity is O(n times log M) and the space complexity is O(log M), where n and M are the length of the array and the maximum value of the elements in the array, respectively.
Similar Problems:
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n), as each element is processed at most twice. |
| Brute Force Method | Time Complexity: O(n^2), as it checks each subarray. |
| Two Pointers + Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Scan | O(n^2 * 32) | O(1) | Small input sizes or when verifying correctness before optimizing |
| Sliding Window with Bit Counters | O(n * 32) | O(32) | General case and optimal solution for large arrays |
Video Solution
Shortest Subarray With OR at Least K II - Leetcode 3097 - Python • NeetCodeIO • 10,256 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shortest Subarray With OR at Least K II easy or hard?
Shortest Subarray With OR at Least K II Python/Java solution
How to solve Shortest Subarray With OR at Least K II in O(n)?
What is the best approach for Shortest Subarray With OR at Least K II?
Is Shortest Subarray With OR at Least K II asked at Google/Amazon/Meta?
What data structure is used in Shortest Subarray With OR at Least K II?
What is the time complexity of Shortest Subarray With OR at Least K II?
Ready to solve this problem?
Practice Shortest Subarray With OR at Least K II with our built-in code editor and test cases.
Practice on FleetCode