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 arrayanswer of sizen whereanswer[i]_is the length of theminimum sized subarray starting at _i withmaximum bitwise OR.

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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5

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^5
  • 0 <= nums[i] <= 10^9

Solution

Method 1 – Bit Tracking from Right to Left

Intuition

To find the smallest subarray starting at each index with the maximum OR, we can process the array from right to left, tracking for each bit the rightmost position where it appears. The answer for each index is the farthest right position needed to cover all bits in the maximum OR.

Approach

  1. Initialize an array pos of size 32 (for each bit) to -1.
  2. Iterate from right to left:
    • For each bit set in nums[i], update pos[bit] = i.
    • For each bit, if pos[bit] != -1, keep the farthest position.
    • The answer for i is the farthest position - i + 1.
  3. Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> pos(32, -1), ans(n, 1);
        for (int i = n-1; i >= 0; --i) {
            for (int b = 0; b < 32; ++b)
                if (nums[i] & (1<<b)) pos[b] = i;
            int far = i;
            for (int b = 0; b < 32; ++b)
                if (pos[b] != -1) far = max(far, pos[b]);
            ans[i] = far - i + 1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func smallestSubarrays(nums []int) []int {
    n := len(nums)
    pos := make([]int, 32)
    for i := range pos { pos[i] = -1 }
    ans := make([]int, n)
    for i := n-1; i >= 0; i-- {
        for b := 0; b < 32; b++ {
            if nums[i]&(1<<b) != 0 { pos[b] = i }
        }
        far := i
        for b := 0; b < 32; b++ {
            if pos[b] != -1 && pos[b] > far { far = pos[b] }
        }
        ans[i] = far - i + 1
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] pos = new int[32], ans = new int[n];
        Arrays.fill(pos, -1);
        for (int i = n-1; i >= 0; --i) {
            for (int b = 0; b < 32; ++b)
                if ((nums[i] & (1<<b)) != 0) pos[b] = i;
            int far = i;
            for (int b = 0; b < 32; ++b)
                if (pos[b] != -1 && pos[b] > far) far = pos[b];
            ans[i] = far - i + 1;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun smallestSubarrays(nums: IntArray): IntArray {
        val n = nums.size
        val pos = IntArray(32) { -1 }
        val ans = IntArray(n)
        for (i in n-1 downTo 0) {
            for (b in 0 until 32) if ((nums[i] shr b) and 1 == 1) pos[b] = i
            var far = i
            for (b in 0 until 32) if (pos[b] != -1 && pos[b] > far) far = pos[b]
            ans[i] = far - i + 1
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def smallestSubarrays(self, nums: list[int]) -> list[int]:
        n = len(nums)
        pos = [-1]*32
        ans = [1]*n
        for i in range(n-1, -1, -1):
            for b in range(32):
                if nums[i] & (1<<b): pos[b] = i
            far = i
            for b in range(32):
                if pos[b] != -1 and pos[b] > far: far = pos[b]
            ans[i] = far - i + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn smallest_subarrays(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut pos = vec![-1; 32];
        let mut ans = vec![1; n];
        for i in (0..n).rev() {
            for b in 0..32 {
                if nums[i] & (1<<b) != 0 { pos[b] = i as i32; }
            }
            let mut far = i as i32;
            for b in 0..32 {
                if pos[b] != -1 && pos[b] > far { far = pos[b]; }
            }
            ans[i] = far - i as i32 + 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    smallestSubarrays(nums: number[]): number[] {
        const n = nums.length;
        const pos = Array(32).fill(-1);
        const ans = Array(n).fill(1);
        for (let i = n-1; i >= 0; --i) {
            for (let b = 0; b < 32; ++b)
                if ((nums[i] & (1<<b)) !== 0) pos[b] = i;
            let far = i;
            for (let b = 0; b < 32; ++b)
                if (pos[b] !== -1 && pos[b] > far) far = pos[b];
            ans[i] = far - i + 1;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n*B), where n is the length of nums and B is the number of bits (32). Each index and bit is processed once.
  • 🧺 Space complexity: O(B), for the bit position array.