algoadvance

Given an array of non-negative integers nums and an integer K, find the length of the shortest, non-empty subarray of nums such that the bitwise OR of every element in the subarray is at least K. If no such subarray exists, return -1.

Clarifying Questions

1. Q: Can elements in nums be zero?
   • A: Yes, they can be. The array contains non-negative integers, including zero.
2. Q: What range of values can K have?
   • A: K can be any non-negative integer.
3. Q: Can K be zero?
   • A: Yes, K can also be zero. In which case, any non-empty subarray will meet the condition.
4. Q: What should we return if no subarray meets the requirement?
   • A: Return -1.
5. Q: What is the maximum length of the array nums?
   • A: This isn’t specified, but we will assume it fits in the memory constraints typical for LeetCode problems.

Strategy

1. Initialization:
   • Start with left and right pointers for a sliding window (both initialized to 0).
   • Use a variable to maintain the current OR value of the subarray.
2. Expanding the Window:
   • Expand the window to the right by moving the right pointer and updating the OR.
3. Validating the Window:
   • Whenever the current OR satisfies the condition (i.e., it’s at least K), try to minimize the window by moving the left pointer to the right while keeping the condition satisfied.
4. Updating the Result:
   • Keep track of the minimum length of all valid windows.
5. Stopping Condition:
   • If we have moved through the entire array, return the minimum length found. If no window meets the condition, return -1.

Code

def shortest_subarray_with_or_at_least_k(nums, K):
    n = len(nums)
    min_len = float('inf')
    current_or = 0
    left = 0

    for right in range(n):
        current_or |= nums[right]  # Expand the window
        
        while left <= right and current_or >= K:  # Contract the window
            min_len = min(min_len, right - left + 1)
            current_or ^= nums[left]  # Remove the leftmost element from OR
            left += 1
            
    return min_len if min_len != float('inf') else -1

# Example usage:
nums = [1, 2, 3, 4, 5]
K = 7
print(shortest_subarray_with_or_at_least_k(nums, K))  # Output: Expected subarray length

Time Complexity

• Time Complexity: O(n), where n is the length of the array. This is because each element is processed at most twice (once when expanding the window and once when contracting).
• Space Complexity: O(1), since we use a constant amount of extra space.

The sliding window approach ensures that we efficiently find the shortest subarray by maintaining the minimal required checks and updates.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?