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

Smallest Subarrays With Maximum Bitwise OR

Number: 2498

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of non-negative integers, for each index i (0-indexed), determine the length of the smallest non-empty subarray starting at index i whose bitwise OR is equal to the maximum bitwise OR obtainable from any subarray that starts at i. In other words, compute for each i the minimal j such that the subarray nums[i...j] gives the same OR as nums[i...n-1].

Key Insights

  • The bitwise OR operation is monotonic; adding more numbers never removes bits already set.
  • The maximum bitwise OR for subarrays starting at index i is achieved by OR-ing all numbers from i to the end.
  • We need to determine the earliest index j such that the OR from i to j already contains all bits present from i to n-1.
  • Maintaining and updating the last seen index for each bit (0 to 31) as we traverse backwards lets us quickly compute the required end index.
  • This approach guarantees an efficient solution since we only iterate over the array (with a constant factor for 32 bits).

Space and Time Complexity

Time Complexity: O(n * B) where B is the number of bits (which is constant, typically 32), so effectively O(n).
Space Complexity: O(n) for the answer array plus O(B) for bit tracking.

Solution

We reverse traverse the input array while maintaining an array to track the most recent occurrence (index) for each bit (0 through 31). For each index i, update the tracking array for the bits present in nums[i] and update a running OR value that represents the global OR from i to the end. To determine the minimum subarray length starting at i that reaches the global OR, for every bit set in the running OR, look up its latest occurrence and take the maximum of these indices. The difference between this maximum index and i (plus one) is the required smallest subarray length.

Code Solutions

# Python implementation with detailed comments
def smallestSubarrays(nums):
    n = len(nums)
    answer = [0] * n  # Initialize answer array
    last_occurrence = [-1] * 32  # Tracks last occurrence for each bit (0 to 31)
    current_or = 0  # Global OR from i to end

    # Traverse from the end to the beginning
    for i in range(n - 1, -1, -1):
        # Update last occurrence for bits present in nums[i]
        for bit in range(32):
            if nums[i] & (1 << bit):
                last_occurrence[bit] = i
        # Update running OR (global OR for subarray starting at i)
        current_or |= nums[i]

        # Determine the farthest index needed to include all bits in current_or
        farthest = i
        for bit in range(32):
            if current_or & (1 << bit):
                farthest = max(farthest, last_occurrence[bit])
        # Store the length of the subarray from i to farthest index (inclusive)
        answer[i] = farthest - i + 1
    return answer

# Example test cases
print(smallestSubarrays([1,0,2,1,3]))  # Expected output: [3,3,2,2,1]
print(smallestSubarrays([1,2]))        # Expected output: [2,1]
← Back to All Questions