Smallest Subarrays With Maximum Bitwise OR

MEDIUM

Description

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 B_ij 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(B_ik) 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 <= 10⁵
0 <= nums[i] <= 10⁹

Approaches

Checkout 3 different approaches to solve Smallest Subarrays With Maximum Bitwise OR. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

A straightforward brute-force approach is to simulate the process described in the problem for each starting index i. For each i, we first need to find the target maximum OR value. This value is the bitwise OR of all elements from nums[i] to the end of the array. After finding this target value, we can then find the shortest subarray starting at i that produces this OR value by iterating from i outwards and stopping as soon as the target OR is achieved.

Algorithm

For each starting index i from 0 to n-1:
- First, determine the maximum possible bitwise OR for any subarray starting at i. Since the bitwise OR operation is monotonic (the OR value never decreases as we add more elements), this maximum OR will be the OR of the entire suffix nums[i...n-1]. Let's call this max_or.
  - To calculate max_or, initialize a variable to 0 and iterate from k = i to n-1, ORing each nums[k] into it.
- Next, find the smallest subarray nums[i...j] that achieves this max_or.
  - Initialize a current_or to 0. Iterate with j from i to n-1.
  - In each step, update current_or by ORing it with nums[j].
  - The first time current_or equals max_or, we have found the smallest j. The length of this subarray is j - i + 1.
  - Store this length in answer[i] and break the inner loop to proceed to the next i.

This method involves a nested loop structure. The outer loop iterates through each possible starting index i of a subarray. For each i, the first inner loop calculates the maximum possible bitwise OR for a subarray starting at i, which is the OR of the entire suffix nums[i...n-1]. The second inner loop then finds the smallest subarray nums[i...j] whose bitwise OR equals this maximum value. The length j - i + 1 is then recorded as the answer for index i.

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            // 1. Calculate the maximum OR for the suffix starting at i
            int maxOr = 0;
            for (int k = i; k < n; k++) {
                maxOr |= nums[k];
            }

            // 2. Find the smallest subarray starting at i that achieves this maxOr
            int currentOr = 0;
            for (int j = i; j < n; j++) {
                currentOr |= nums[j];
                if (currentOr == maxOr) {
                    answer[i] = j - i + 1;
                    break;
                }
            }
        }
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the `nums` array. For each index `i`, we iterate up to two times over the suffix `nums[i...n-1]`, leading to a quadratic time complexity.Space Complexity: O(N) for the output array. If the output array is not considered, the space complexity is O(1).

Pros and Cons

Pros:

Simple to understand and implement.
Correctly solves the problem for small input sizes.

Cons:

The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5), leading to a 'Time Limit Exceeded' error on larger test cases.

Code Solutions

Checking out 3 solutions in different languages for Smallest Subarrays With Maximum Bitwise OR. Click on different languages to view the code.

class Solution {
public
  int[] smallestSubarrays(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    int[] f = new int[32];
    Arrays.fill(f, -1);
    for (int i = n - 1; i >= 0; --i) {
      int t = 1;
      for (int j = 0; j < 32; ++j) {
        if (((nums[i] >> j) & 1) == 1) {
          f[j] = i;
        } else if (f[j] != -1) {
          t = Math.max(t, f[j] - i + 1);
        }
      }
      ans[i] = t;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Smallest Subarrays With Maximum Bitwise OR

Algorithms:

Binary Search

Patterns:

Sliding WindowBit Manipulation

Data Structures:

Array