LeetCode 2411 - Smallest Subarrays With Maximum Bitwise OR

The problem asks us to find, for each index in a given array nums, the length of the shortest contiguous subarray starting at that index whose bitwise OR is equal to the maximum possible bitwise OR obtainable from that index onward.

leetcodemediumarraybinary-searchbit-manipulationsliding-window

LeetCode Problem 2411

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Bit Manipulation, Sliding Window

Solution

Problem Understanding

The problem asks us to find, for each index in a given array nums, the length of the shortest contiguous subarray starting at that index whose bitwise OR is equal to the maximum possible bitwise OR obtainable from that index onward. In other words, we need to look at all subarrays that start at i, compute their bitwise OR, and find the smallest subarray whose OR reaches the maximum achievable from i to the end of the array.

The input is a 0-indexed array of non-negative integers. The output is an array of the same size, where each element represents the minimum subarray length for that starting index that achieves the maximum bitwise OR.

Constraints tell us that n can be as large as 100,000, and elements can be up to 1 billion. This implies that a naive solution iterating over all subarrays is infeasible due to O(n^2) complexity. Edge cases that can trip up a naive approach include arrays with repeated numbers, all zeros, or arrays where the maximum OR is only achieved at the last element.

Approaches

The brute-force approach involves iterating through each index, computing the OR of every possible subarray starting at that index, and then selecting the smallest length that achieves the maximum OR. While correct, this approach has O(n^2) time complexity and is too slow for large arrays.

The optimal approach leverages the fact that the bitwise OR operation is monotonic: once a bit is set to 1 in a cumulative OR, it cannot be unset by including more elements. This allows us to compute the maximum OR achievable from each index and then determine the minimum subarray length in reverse order. We maintain the most recent position of each bit to compute the minimum length needed for that bit to appear in the OR.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Compute OR for all subarrays starting at each index
Optimal O(n * B) O(B) Track last occurrence of each bit, compute minimum length using bit positions (B = number of bits, ≤ 30)

Algorithm Walkthrough

  1. Initialize an array answer of length n to store the results.
  2. Create an array nextPos of size 30 (for 30 bits since nums[i] <= 10^9) to track the next occurrence of each bit, initialized with n (beyond the last index).
  3. Traverse the array from right to left (starting at index n-1) to update nextPos for each bit present in nums[i].
  4. For each index i, determine the farthest position any bit needs to extend to achieve maximum OR by looking at nextPos. The minimum subarray length is farthest - i + 1.
  5. Update nextPos to reflect that the bits in nums[i] are now seen at index i.
  6. Continue until index 0 is processed. Return the answer array.

Why it works: Bitwise OR is monotonic. By tracking the last positions of each bit set to 1, we guarantee that including all elements up to the farthest bit's next position produces the maximum OR. Since we traverse from right to left, we always have the correct “future” positions available to compute the minimum length.

Python Solution

from typing import List

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [0] * n
        B = 30  # maximum number of bits to consider
        nextPos = [n] * B  # next position where each bit is set
        
        for i in range(n-1, -1, -1):
            farthest = i
            for bit in range(B):
                if (nums[i] >> bit) & 1:
                    nextPos[bit] = i
                if nextPos[bit] < n:
                    farthest = max(farthest, nextPos[bit])
            answer[i] = farthest - i + 1
        
        return answer

Explanation: We initialize nextPos to track the latest occurrence of each bit. Iterating backwards, we update nextPos for each bit in the current number. farthest keeps track of the maximum index any required bit appears at or after the current index. The subarray length is then farthest - i + 1. This efficiently computes the minimum length subarray achieving maximum OR for each starting index.

Go Solution

func smallestSubarrays(nums []int) []int {
    n := len(nums)
    answer := make([]int, n)
    B := 30
    nextPos := make([]int, B)
    for i := 0; i < B; i++ {
        nextPos[i] = n
    }

    for i := n - 1; i >= 0; i-- {
        farthest := i
        for bit := 0; bit < B; bit++ {
            if (nums[i]>>bit)&1 == 1 {
                nextPos[bit] = i
            }
            if nextPos[bit] < n {
                if nextPos[bit] > farthest {
                    farthest = nextPos[bit]
                }
            }
        }
        answer[i] = farthest - i + 1
    }
    return answer
}

Explanation: The Go implementation mirrors Python. We use slices for answer and nextPos. Integer arithmetic and bit shifting works identically. The only difference is explicit initialization of slices and conditional comparisons using == 1.

Worked Examples

Example 1: nums = [1,0,2,1,3]

i nums[i] nextPos farthest answer[i]
4 3 [5,...] 4 1
3 1 [3,...] 4 2
2 2 [2,...] 3 2
1 0 [2,...] 3 3
0 1 [0,...] 2 3

Output: [3,3,2,2,1]

Example 2: nums = [1,2]

i nums[i] nextPos farthest answer[i]
1 2 [2,...] 1 1
0 1 [0,1...] 1 2

Output: [2,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n * B) Each index checks at most 30 bits; B is 30 for 10^9 max value
Space O(B + n) nextPos of size B, answer array of size n

The algorithm is linear in n with a small constant factor B, making it efficient for the input constraints.

Test Cases

# Provided examples
assert Solution().smallestSubarrays([1,0,2,1,3]) == [3,3,2,2,1]  # Example 1
assert Solution().smallestSubarrays([1,2]) == [2,1]  # Example 2

# Edge cases
assert Solution().smallestSubarrays([0]) == [1]  # single element
assert Solution().smallestSubarrays([1,1,1,1]) == [1,1,1,1]  # all same elements
assert Solution().smallestSubarrays([1,0,0,0,0,0,1023]) == [7,6,5,4,3,2,1]  # max at the end
assert Solution().smallestSubarrays([1<<29, 1<<29, 1<<29]) == [1,1,1]  # large bit numbers
Test Why
[1,0,2,1,3] Standard example with mixed values
[1,2] Small array
[0] Single element
[1,1,1,1] Repeated elements
[1,0,0,0,0,0,1023] Max at the end, longest subarray
[1<<29,1<<29,1<<29] Test high bit numbers

Edge Cases

One important edge case is a single-element array. The smallest subarray is trivially of length 1, and the maximum OR is the element itself. Our implementation correctly handles this by initializing farthest = i.

Another edge case is when the maximum OR occurs at the last element of the array, which requires subarrays starting at earlier indices to extend all the way to the end. Using nextPos ensures we correctly compute the farthest bit positions and hence the minimum subarray length.

A third edge case involves numbers with high bits set, close to 10^9. The algorithm