Count subarrays with majority element ii

Array Hash Table Divide and Conquer Segment Tree Merge Sort Prefix Sum

44.5% acceptance

Feb 24, 2026

You are given an integer array nums and an integer target. Return the number of subarrays of nums in which target is the majority element. The majority element of a subarray is the element that appears strictly more than half of the times.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_majority_subarrays(nums: Vec<i32>, target: i32) -> i64 {
    // Subarray [l,r] has target as majority iff count(target in [l,r]) * 2 > r - l + 1
    // Let prefix[i] = number of target occurrences in nums[0..i]
    // Condition: 2*(prefix[r+1] - prefix[l]) > (r+1) - l
    //   => 2*prefix[r+1] - (r+1) > 2*prefix[l] - l
    // Define g(i) = 2*prefix[i] - i.
    // Answer = number of pairs (i < j) with g[j] > g[i].
    //
    // O(n log n): use a Fenwick tree on coordinate-compressed g values.
    // g[i] = 2*prefix[i] - i, range: [-n, 2n]. Shift by +n so values in [0, 3n].
    let n = nums.len();
    let offset = n as i32; // shift g values to be non-negative
    let size = 3 * n + 2;
    let mut bit = vec![0i64; size + 2];

    // Fenwick tree update: add 1 at position pos (0-indexed)
    macro_rules! bit_add {
      ($pos:expr) => {{
        let mut p = $pos + 1usize;
        while p <= size {
          bit[p] += 1;
          p += p & p.wrapping_neg();
        }
      }};
    }
    // Fenwick tree prefix-sum query: sum over [0, pos] (0-indexed)
    macro_rules! bit_sum {
      ($pos:expr) => {{
        let mut p = $pos + 1usize;
        let mut s = 0i64;
        while p > 0 {
          s += bit[p];
          p -= p & p.wrapping_neg();
        }
        s
      }};
    }

    // Insert g[0] = 2*0 - 0 + offset = offset (= n)
    bit_add!(offset as usize);

    let mut prefix = 0i32;
    let mut ans = 0i64;
    for i in 0..n {
      prefix += if nums[i] == target { 1 } else { 0 };
      let g = (2 * prefix - (i as i32 + 1) + offset) as usize;
      // Count previously inserted g[j] values strictly less than g
      if g > 0 {
        ans += bit_sum!(g - 1);
      }
      bit_add!(g);
    }
    ans
  }
}