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.
1def shortest_subarray_with_or_at_least_k(nums, k):
2 left, curr_or, min_length = 0, 0, float('inf')
3 for right in range(len(nums)):
4 curr_or |= nums[right]
5 while curr_or >= k and left <= right:
6 min_length = min(min_length, right - left + 1)
7 curr_or ^= nums[left]
8 left += 1
9 return -1 if min_length == float('inf') else min_length
10
11nums = [1, 2, 3]
12k = 2
13print(shortest_subarray_with_or_at_least_k(nums, k)) # Output: 1
14The Python version initializes a variable for the current OR and iterates through the array like previous instances, but using Python's flexible range and list indexing. It uses conditional checks to see if removing the start of the subarray still meets or exceeds the condition.
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
public class ShortestSubarraySolver {
public static int ShortestSubarrayWithORAtLeastK(int[] nums, int k) {
int minLength = int.MaxValue;
for (int start = 0; start < nums.Length; ++start) {
int currOR = 0;
for (int end = start; end < nums.Length; ++end) {
currOR |= nums[end];
if (currOR >= k) {
minLength = Math.Min(minLength, end - start + 1);
break;
}
}
}
return minLength == int.MaxValue ? -1 : minLength;
}
static void Main() {
int[] nums = {1, 2, 3};
int k = 2;
Console.WriteLine(ShortestSubarrayWithORAtLeastK(nums, k)); // Output: 1
}
}
This C# brute force solution methodically assesses all subarray OR values against k. It collects the minimal length with each valid discovery using nested iterations.