3737. Count Subarrays With Majority Element I

MediumView on LeetCode

Array Prefix Sum Binary Indexed Tree

Time: O(n log n)

Space: O(n)

Problem Overview

Target is a strict majority in subarray [l, r] when its count exceeds half the length.

Intuition

Target is a strict majority in subarray [l, r] when its count exceeds half the length. Encode +1 for target and −1 for every other value: the subarray sum is positive exactly in that case (2·count − length > 0). Scan left to right with a running prefix sum s; each new position starts subarrays ending here whose earlier prefix is strictly less than s — count those with a Fenwick tree on shifted indices.

Algorithm

1Initialize Fenwick tree and prefix sum s = n + 1 (offset so indices stay positive).
2Record one occurrence of the empty prefix: tree.Update(s, 1).
3For each x in nums: s += 1 if x == target else −1.
4Add tree.Query(s − 1) to the answer (earlier prefixes smaller than current).
5tree.Update(s, 1) and continue.
6Return the total count.

Example Walkthrough

Input: nums = [1,2,2,3], target = 2

1.Subarrays where 2 is strict majority: [2,2], [2,2,3], [1,2,2], [1,2,2,3] — four total.
2.Transformed +1/−1 prefix sums stay positive only on those windows.

Output: 4

Common Pitfalls

•Strict majority needs sum > 0, not ≥ 0 — query prefixes < s, not ≤ s.
•Offset prefix sums by n + 1 so Fenwick indices never go negative.
•Use long for the answer if n is large; counts can exceed int.

3737.cs

// Approach: Map target to +1 and other values to -1. A subarray has a strict majority of target
// iff the transformed sum is positive. Count subarrays with positive sum using prefix sums and a Fenwick tree.
// Time: O(n log n) Space: O(n)
public class Solution
{
    public int CountMajoritySubarrays(int[] nums, int target)
    {
        int n = nums.Length;
        BinaryIndexedTree tree = new BinaryIndexedTree(2 * n + 1);
        int s = n + 1;
        tree.Update(s, 1);
        long ans = 0;
        foreach (int x in nums)
        {
            s += x == target ? 1 : -1;
            ans += tree.Query(s - 1);
            tree.Update(s, 1);
        }
        return (int)ans;
    }
}

class BinaryIndexedTree
{
    private int n;
    private int[] c;

    public BinaryIndexedTree(int n)
    {
        this.n = n;
        this.c = new int[n + 1];
    }

    public void Update(int x, int delta)
    {
        for (; x <= n; x += x & -x)
            c[x] += delta;
    }

    public int Query(int x)
    {
        int s = 0;
        for (; x > 0; x -= x & -x)
            s += c[x];
            
        return s;
    }
}

Was this solution helpful?