Smallest subarrays with maximum bitwise or

Array Binary Search Bit Manipulation Sliding Window

62.0% acceptance

Feb 25, 2026

1044

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 a subarray [l, r] is nums[l] OR nums[l + 1] OR ... OR nums[r]. Return an integer array answer of size n where answer[i] is the length of the minimum sized subarray starting at index i with maximum bitwise OR.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_subarrays(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    // last[b] = last index where bit b is set; use n (sentinel = "not found")
    let mut last = [n; 32];
    let mut ans = vec![1i32; n];
    for i in (0..n).rev() {
      for b in 0..32 {
        if nums[i] & (1 << b) != 0 {
          last[b] = i;
        }
      }
      let farthest = last.iter().filter(|&&v| v != n).copied().max();
      if let Some(f) = farthest {
        ans[i] = (f - i + 1) as i32;
      }
      // else: all bits zero from here to end, so ans[i] = 1 (already set)
    }
    ans
  }
}