Sponsored
Sponsored
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.
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.
1#include <stdio.h>
2#include <limits.h>
3
4int shortestSubarrayWithORAtLeastK(int* nums, int numsSize, int k) {
5 int left = 0, currOR = 0, minLength = INT_MAX;
6 for (int right = 0; right < numsSize; ++right) {
7 currOR |= nums[right];
8 while (currOR >= k && left <= right) {
9 minLength = (right - left + 1) < minLength ? (right - left + 1) : minLength;
10 currOR ^= nums[left++];
11 }
12 }
13 return minLength == INT_MAX ? -1 : minLength;
14}
15
16int main() {
17 int nums[] = {1, 2, 3};
18 int k = 2;
19 printf("%d\n", shortestSubarrayWithORAtLeastK(nums, 3, k)); // Output: 1
20 return 0;
21}
22This 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.
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.
Time Complexity: O(n^2), as it checks each subarray.
Space Complexity: O(1), with basic indexing variables used.
1
Aimed at known subarray evaluations, this Python brute force solution examines every potential subarray OR total, logging the minimum length that satisfies k. The nested loop structure identifies all start-point possibilities and computes correspondingly.