We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Subarray With OR at Least K II

Number: 3380

Difficulty: Medium

Paid? No

Companies: Google, Meta, Mitsogo

Problem Description

Given an array of non-negative integers, find the length of the shortest non-empty contiguous subarray such that the bitwise OR of all its elements is at least k. If no such subarray exists, return -1.

Key Insights

  • The OR operation is cumulative but not invertible; meaning when sliding a window, removing an element does not simply subtract its contribution.
  • We can combine current numbers with previously computed ORs from subarrays ending at prior positions.
  • By maintaining a list of OR-values and their corresponding subarray lengths for subarrays ending at the current index, we can update these values efficiently.
  • Redundant OR values (duplicates) can be pruned to keep the dynamic programming state minimal.
  • The solution leverages bit manipulation with a dynamic programming approach that iterates through the array while updating the best (shortest) subarray length.

Space and Time Complexity

Time Complexity: O(n * B) where B is the number of bits (in practice at most 32), so effectively O(n).
Space Complexity: O(n) in worst-case scenario, but typically much less as updates merge redundant states.

Solution

We iterate over the array and for each element, we form a new set of subarrays ending at that element by taking the current element alone and by appending it to each subarray ending at the previous index. We compute the new OR value when combining and update the minimal length when the OR reaches at least k. Redundant or duplicate OR values with no advantage in length are removed to keep the state small. This dynamic programming method ensures that we explore all subarrays ending at the current index without needing to re-start from scratch.

Code Solutions

# Python solution using dynamic programming approach with list tracking last OR values for ending subarrays.
def shortestSubarrayWithOrAtLeastK(nums, k):
    dp = []  # List of tuples: (current OR value, length of subarray ending here)
    best = float('inf')
    
    for num in nums:
        new_dp = []
        # Start a new subarray with the current number.
        new_dp.append((num, 1))
        if num >= k:
            best = 1
        
        # Extend previous subarrays by including the current number.
        for or_val, length in dp:
            new_or = or_val | num
            new_length = length + 1
            # If the same OR value exists, take the one with the shorter length.
            if new_dp and new_dp[-1][0] == new_or:
                new_dp[-1] = (new_or, min(new_dp[-1][1], new_length))
            else:
                new_dp.append((new_or, new_length))
            if new_or >= k:
                best = min(best, new_length)
        
        # Remove redundant states with identical OR values.
        dp = []
        for or_val, length in new_dp:
            if dp and dp[-1][0] == or_val:
                dp[-1] = (or_val, min(dp[-1][1], length))
            else:
                dp.append((or_val, length))
    
    return best if best != float('inf') else -1

# Example usage:
print(shortestSubarrayWithOrAtLeastK([1,2,3], 2))
← Back to All Questions