3739. Count Subarrays With Majority Element II

Time: O(n log n)

Space: O(n)

Problem Overview

Identical counting rule to LC 3737: target is a strict majority in a subarray when +1/−1 encoding yields a positive sum.

Intuition

Identical counting rule to LC 3737: target is a strict majority in a subarray when +1/−1 encoding yields a positive sum. Use a Fenwick tree over shifted prefix sums to count how many earlier prefixes are strictly smaller than the current one. Part II only changes constraints — the answer can exceed 32-bit range, so accumulate in long and return long from CountMajoritySubarrays.

Algorithm

1Same pipeline as 3737: offset prefix s = n + 1, seed empty prefix in the BIT.
2For each value: update s (+1 for target, −1 otherwise).
3ans += Query(s − 1); Update(s, 1).
4Return ans as long.

Example Walkthrough

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

1.Four subarrays have 2 as strict majority — same as problem I.
2.With larger n the count may overflow int; long prevents wraparound.

Output: 4

Common Pitfalls

•Do not cast the Fenwick accumulation to int before returning.
•BIT frequency array can stay int; only the running answer needs long.
•Query(s − 1), not Query(s), for strict majority (positive sum, not zero).

3739.cs

// Approach: Same as LC 3737 — map target to +1, others to −1; count subarrays with positive
// transformed sum via prefix sums and a Fenwick tree. Return long for large answer counts.
// Time: O(n log n) Space: O(n)
public class Solution
{
    public long 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 ans;
    }
}

public 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?