Count good subarrays

Array Stack Bit Manipulation Monotonic Stack

23.7% acceptance

Mar 31, 2026

You are given an integer array nums. A subarray is called good if the bitwise OR of all its elements is equal to at least one element present in that subarray. Return the number of good subarrays in nums. Here, the bitwise OR of two integers a and b is denoted by a | b.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_good_subarrays(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    let mut count = 0i64;
    
    // Good subarray [l..=r]: OR(l..=r) == max(l..=r).
    // Use OR segments trick: track (or_val, max_val, leftmost_l) per segment.
    // Segments ordered from largest l to smallest l.
    // Segment i covers l in [new_segs[i].2, right_bound]:
    //   i == 0: right_bound = r, count = r - new_segs[0].2 + 1
    //   i > 0: right_bound = new_segs[i-1].2 - 1, count = new_segs[i-1].2 - new_segs[i].2
    
    let mut segments: Vec<(i32, i32, usize)> = Vec::new();
    
    for r in 0..n {
      let mut new_segs: Vec<(i32, i32, usize)> = Vec::new();
      new_segs.push((nums[r], nums[r], r));
      
      for &(or_v, mx_v, start) in &segments {
        let new_or = or_v | nums[r];
        let new_mx = mx_v.max(nums[r]);
        if let Some(last) = new_segs.last_mut() {
          if last.0 == new_or && last.1 == new_mx {
            last.2 = start;
            continue;
          }
        }
        new_segs.push((new_or, new_mx, start));
      }
      
      for i in 0..new_segs.len() {
        if new_segs[i].0 == new_segs[i].1 {
          let cnt = if i == 0 {
            (r - new_segs[0].2 + 1) as i64
          } else {
            (new_segs[i - 1].2 - new_segs[i].2) as i64
          };
          count += cnt;
        }
      }
      
      segments = new_segs;
    }
    
    count
  }
}