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 <= 109The 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), as it checks each subarray.
Space Complexity: O(1), with basic indexing variables used.
| 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. |
Shortest Subarray with Sum at Least K - Leetcode 862 - Python • NeetCodeIO • 19,043 views views
Watch 9 more video solutions →Practice Shortest Subarray With OR at Least K II with our built-in code editor and test cases.
Practice on FleetCode