{x}
blog image

Smallest Subarrays With Maximum Bitwise OR

You are given a 0-indexed array nums of length n, consisting of non-negative integers. For each index i from 0 to n - 1, you must determine the size of the minimum sized non-empty subarray of nums starting at i (inclusive) that has the maximum possible bitwise OR.

  • In other words, let Bij be the bitwise OR of the subarray nums[i...j]. You need to find the smallest subarray starting at i, such that bitwise OR of this subarray is equal to max(Bik) where i <= k <= n - 1.

The bitwise OR of an array is the bitwise OR of all the numbers in it.

Return an integer array answer of size n where answer[i] is the length of the minimum sized subarray starting at i with maximum bitwise OR.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,0,2,1,3]
Output: [3,3,2,2,1]
Explanation:
The maximum possible bitwise OR starting at any index is 3. 
- Starting at index 0, the shortest subarray that yields it is [1,0,2].
- Starting at index 1, the shortest subarray that yields the maximum bitwise OR is [0,2,1].
- Starting at index 2, the shortest subarray that yields the maximum bitwise OR is [2,1].
- Starting at index 3, the shortest subarray that yields the maximum bitwise OR is [1,3].
- Starting at index 4, the shortest subarray that yields the maximum bitwise OR is [3].
Therefore, we return [3,3,2,2,1].

Example 2:

Input: nums = [1,2]
Output: [2,1]
Explanation:
Starting at index 0, the shortest subarray that yields the maximum bitwise OR is of length 2.
Starting at index 1, the shortest subarray that yields the maximum bitwise OR is of length 1.
Therefore, we return [2,1].

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 0 <= nums[i] <= 109

Solution Explanation:

The problem asks to find the smallest subarray starting from each index i that has the maximum possible bitwise OR. The key insight is that we can process the array from right to left, efficiently tracking the rightmost occurrence of each bit.

Algorithm:

  1. Initialization: Create an array ans of the same size as nums to store the results. Initialize it with 1s, representing the minimum length if the maximum OR is achieved with just the single element at the index. Create an array f of size 32 (representing the bits) initialized with -1. This array f will store the rightmost index where each bit is set to 1.

  2. Reverse Traversal: Iterate through nums from right to left (index i from n-1 down to 0).

  3. Bitwise OR and Length Calculation: For each number nums[i]:

    • Iterate through the bits (from 0 to 31).
    • If the j-th bit of nums[i] is 1, update f[j] to i (this is the new rightmost occurrence of that bit).
    • If the j-th bit of nums[i] is 0, but f[j] is not -1 (meaning that bit is set to 1 somewhere to the right), the shortest subarray containing that bit must extend at least from f[j] to i. Therefore, update t = max(t, f[j] - i + 1), where t keeps track of the maximum length needed to include all bits set to 1.

  4. Store Result: After checking all bits for nums[i], assign ans[i] = t. This represents the minimum length of the subarray starting at i that achieves the maximum bitwise OR.

Time Complexity: O(n * log(m)), where n is the length of nums and m is the maximum value in nums. The outer loop iterates n times, and the inner loop iterates at most log(m) times (number of bits in m).

Space Complexity: O(1). The space used by ans and f is constant, irrespective of input size. We only need 32 elements for f to cover all 32 bits.

Code in Different Languages:

The code implementations provided in the previous response are accurate and efficient representations of the algorithm. They effectively demonstrate the solution in Python, Java, C++, and Go. No further modifications are needed.