Scale Engineer

Smallest Subarrays With Maximum Bitwise OR

Med
#2195Time: 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: O(N) for the output array. If the output array is not considered, the space complexity is O(1).
Patterns
Sliding WindowBit Manipulation
Algorithms
Binary Search
Data structures
Array

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(N) for the output array. If the output array is not considered, the space complexity is O(1).

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem