2411. Smallest Subarrays With Maximum Bitwise OR

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⁹

Solutions

Solution 1: Reverse Traversal

Thinking

From each start \(i\), scanning right for the shortest maximum-OR subarray is \(O(n^2)\) and fails at \(n\le 10^5\). The maximum OR from \(i\) is fixed by the leftmost \(1\) of each bit, all of which lie at or to the right of \(i\).

Scan backward and keep, for each of \(32\) bits, the latest index where that bit is \(1\). If the current value already has the bit, update the index; otherwise the window must reach the recorded index. The length is the farthest such reach.

To find the shortest subarray starting at position \(i\) that maximizes the bitwise OR operation, we need to maximize the number of \(1\)s in the result.

We use an array \(f\) of size \(32\) to record the earliest position of each bit \(1\).

We traverse the array \(nums[i]\) in reverse order. For the \(j\)-th bit of \(nums[i]\), if it is \(1\), then \(f[j]\) is \(i\). Otherwise, if \(f[j]\) is not \(-1\), it means that a number satisfying the \(j\)-th bit as \(1\) is found on the right, so we update the length.

The time complexity is \(O(n \times \log m)\), where \(n\) is the length of the array \(nums\), and \(m\) is the maximum value in the array \(nums\).

Python3JavaC++GoTypeScriptRust

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

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

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

func smallestSubarrays(nums []int) []int {
    n := len(nums)
    f := make([]int, 32)
    for i := range f {
        f[i] = -1
    }
    ans := make([]int, n)
    for i := n - 1; i >= 0; i-- {
        t := 1
        for j := 0; j < 32; j++ {
            if ((nums[i] >> j) & 1) == 1 {
                f[j] = i
            } else if f[j] != -1 {
                t = max(t, f[j]-i+1)
            }
        }
        ans[i] = t
    }
    return ans
}

function smallestSubarrays(nums: number[]): number[] {
    const n = nums.length;
    const ans: number[] = Array(n).fill(1);
    const f: number[] = Array(32).fill(-1);

    for (let i = n - 1; i >= 0; i--) {
        let t = 1;
        for (let j = 0; j < 32; j++) {
            if ((nums[i] >> j) & 1) {
                f[j] = i;
            } else if (f[j] !== -1) {
                t = Math.max(t, f[j] - i + 1);
            }
        }
        ans[i] = t;
    }

    return ans;
}

impl Solution {
    pub fn smallest_subarrays(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut ans = vec![1; n];
        let mut f = vec![-1; 32];

        for i in (0..n).rev() {
            let mut t = 1;
            for j in 0..32 {
                if (nums[i] >> j) & 1 != 0 {
                    f[j] = i as i32;
                } else if f[j] != -1 {
                    t = t.max(f[j] - i as i32 + 1);
                }
            }
            ans[i] = t;
        }

        ans
    }
}

2411. Smallest Subarrays With Maximum Bitwise OR

Description

Solutions

Solution 1: Reverse Traversal

Comments