# Smallest Subarrays With Maximum Bitwise OR
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-subarrays-with-maximum-bitwise-or)
Canonical: https://scaleengineer.com/dsa/problems/smallest-subarrays-with-maximum-bitwise-or
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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
## 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.
**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).
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Optimized Brute Force with Suffix ORs
This approach slightly optimizes the brute-force method. Instead of recalculating the maximum suffix OR for each starting index `i` inside the main loop, we can precompute all suffix ORs in a single pass. We can iterate from the end of the array to the beginning, calculating `suffixOr[i]` based on `nums[i]` and `suffixOr[i+1]`. After this precomputation, the main logic remains similar to the brute-force approach.
**Time:** O(N^2). The precomputation takes O(N), but the nested loop to find the minimal subarray for each `i` still dominates, taking O(N^2) time in the worst case. · **Space:** O(N) to store the `suffixOr` array and the `answer` array.
**Pros:** Slightly more efficient in terms of constant factors than the pure brute-force approach.; The logic is still relatively easy to follow.
**Cons:** The overall time complexity is still O(N^2), which is not efficient enough for the given constraints.
### Explanation
The core idea is to separate the calculation of the maximum OR value from the search for the minimal subarray. We can build a `suffixOr` array where `suffixOr[i]` stores the bitwise OR of `nums[i...n-1]`. This can be done in O(N) time by iterating backwards. Once we have this array, for each `i`, we know the target OR is `suffixOr[i]`. We then iterate from `j=i` to find the first `j` where `OR(nums[i...j])` equals `suffixOr[i]`. While this saves redundant calculations of the maximum OR, the search for `j` still results in a nested loop structure.

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

        // Precompute suffix ORs in O(N)
        suffixOr[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixOr[i] = nums[i] | suffixOr[i + 1];
        }

        // Find the smallest subarray for each starting index i
        for (int i = 0; i < n; i++) {
            int targetOr = suffixOr[i];
            int currentOr = 0;
            for (int j = i; j < n; j++) {
                currentOr |= nums[j];
                if (currentOr == targetOr) {
                    answer[i] = j - i + 1;
                    break;
                }
            }
        }
        return answer;
    }
}
```
### Algorithm
- First, precompute the suffix ORs for the entire array. Create an array `suffixOr` of size `n`.
  - `suffixOr[n-1] = nums[n-1]`.
  - Iterate `i` from `n-2` down to `0` and calculate `suffixOr[i] = nums[i] | suffixOr[i+1]`.
- Now, iterate through each starting index `i` from `0` to `n-1`:
  - The target maximum OR for index `i` is `suffixOr[i]`.
  - Find the smallest `j >= i` such that the bitwise OR of `nums[i...j]` equals `suffixOr[i]`.
    - Initialize `currentOr = 0`.
    - Iterate `j` from `i` to `n-1`.
    - Update `currentOr |= nums[j]`.
    - If `currentOr == suffixOr[i]`, we've found our minimal subarray. Set `answer[i] = j - i + 1` and break the inner loop.

## Backward Iteration with Bit Manipulation
The most efficient approach involves iterating through the array backwards and using bit manipulation. The key idea is that for any starting index `i`, the maximum possible OR is fixed (it's the OR of all numbers from `i` to `n-1`). To achieve this OR with the smallest subarray `nums[i...j]`, `j` must be large enough to include at least one number for each bit set in the maximum OR. By iterating backwards, we can maintain the most recent index where each bit has been seen. This allows us to determine the required endpoint `j` for each `i` efficiently.
**Time:** O(N * log C), where N is the number of elements and C is the maximum value in `nums`. Since C is up to 10^9, log C is approximately 30. This makes the complexity effectively linear, O(N). · **Space:** O(N) for the output array. The auxiliary `last` array has a constant size (30), so it's O(1) space.
**Pros:** Highly efficient with a linear time complexity.; Passes all test cases within the time limit.
**Cons:** The logic is more complex and less intuitive than the brute-force approaches.; Requires understanding of bit manipulation and a dynamic programming-like way of thinking.
### Explanation
We iterate from `i = n-1` down to `0`. We maintain an array `last` of size 30, where `last[b]` stores the index of the rightmost element `nums[k]` (with `k >= i`) that has the `b`-th bit set. 

When we are at index `i`, we first update `last` with the bits from `nums[i]`. For any bit `b` set in `nums[i]`, we set `last[b] = i`. After this update, `last[b]` contains the index of the last occurrence of bit `b` in the suffix `nums[i...n-1]`. 

The maximum OR for the suffix `nums[i...n-1]` is composed of all bits `b` for which `last[b]` has been updated to an index `>= i`. To form this OR value, our subarray starting at `i` must extend far enough to cover at least one number for each of these bits. The farthest index we need to reach is simply the maximum value present in our `last` array. Let this be `farthest_index`. The minimal subarray is then `nums[i...farthest_index]`, and its length is `farthest_index - i + 1`.

```java
class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        // last[b] stores the index of the last seen number with the b-th bit set.
        int[] last = new int[30];

        for (int i = n - 1; i >= 0; i--) {
            // Update the last seen index for each bit present in nums[i].
            for (int b = 0; b < 30; b++) {
                if (((nums[i] >> b) & 1) == 1) {
                    last[b] = i;
                }
            }

            // The end of the smallest subarray is determined by the farthest index
            // we need to reach to include all necessary bits.
            int farthestIndex = i;
            for (int b = 0; b < 30; b++) {
                farthestIndex = Math.max(farthestIndex, last[b]);
            }
            
            answer[i] = farthestIndex - i + 1;
        }

        return answer;
    }
}
```
### Algorithm
- We process the array `nums` from right to left, from `i = n-1` down to `0`.
- We use an auxiliary array, `last`, of size 30 (since `nums[i] <= 10^9 < 2^30`). `last[b]` will store the index of the most recent (rightmost) occurrence of a number that has the `b`-th bit set.
- Initialize `last` with all zeros.
- For each index `i` from `n-1` down to `0`:
  - Update the `last` array for the current number `nums[i]`. Iterate through each bit `b` from 0 to 29. If the `b`-th bit is set in `nums[i]`, set `last[b] = i`.
  - The maximum OR for the suffix `nums[i...n-1]` is formed by all bits `b` for which we have seen a number with that bit set in this suffix. The `last` array now holds the rightmost index for each of these bits.
  - To form the maximum OR in the shortest possible subarray starting at `i`, we must extend the subarray to include an occurrence of every necessary bit. The required endpoint `j` will be the maximum of all indices in the `last` array. This is because we need to reach the farthest rightmost occurrence of any bit that contributes to the total OR.
  - Calculate `farthest_index = max(i, max(last[0...29]))`.
  - The length of the smallest subarray is `farthest_index - i + 1`. Store this in `answer[i]`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> smallestSubarrays(vector<int> &nums) {
    int n = nums.size();
    vector<int> f(32, -1);
    vector<int> ans(n);
    for (int i = n - 1; ~i; --i) {
      int t = 1;
      for (int j = 0; j < 32; ++j) {
        if ((nums[i] >> j) & 1) {
          f[j] = i;
        } else if (f[j] != -1) {
          t = max(t, f[j] - i + 1);
        }
      }
      ans[i] = t;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]: n = len(nums) ans = [1] * n f = [- 1] * 32 for i in range(n - 1, - 1, - 1): t = 1 for j in range(32): if (nums[i] >> j) & 1: f[j] = i elif f[j] != - 1: t = max(t, f[j] - i + 1) ans[i] = t return ans

```