Count Subarrays With Majority Element II - Solution & Explanation

Problem Overview: You are given an integer array and need to count subarrays where some element appears strictly more than half of the subarray length (a majority element). The challenge is detecting majority dominance across all possible subarrays without checking every frequency from scratch.

Approach 1: Brute Force Frequency Check (O(n^3) time, O(1) space)

Enumerate every subarray using two nested loops. For each range [l, r], compute element frequencies and check whether any count exceeds (r - l + 1) / 2. This requires scanning the subarray or maintaining a temporary frequency map. While straightforward, it performs a full validation for every possible range and quickly becomes impractical as n grows.

Approach 2: Prefix Frequency + Candidate Tracking (O(n^2) time, O(n) space)

Instead of recomputing frequencies from scratch, maintain incremental counts while expanding the right boundary of a subarray. A hash table tracks element frequencies and updates the current maximum frequency as the window grows. This removes the inner scan but still requires evaluating O(n^2) subarrays. It demonstrates the key observation: majority depends on comparing frequency against half of the window length.

Approach 3: Prefix Balance + Binary Indexed Tree (O(n log n) time, O(n) space)

The optimized approach converts the majority condition into a prefix comparison problem. For a candidate value, map occurrences to +1 and all other values to -1. A subarray has that value as majority if the prefix sum difference between its boundaries is positive. Counting such ranges reduces to counting pairs of prefix sums where the later sum is greater than the earlier one.

A Binary Indexed Tree (Fenwick Tree) efficiently counts how many previous prefix sums are smaller than the current value. Use coordinate compression because prefix values may be negative. Iterate through prefix sums, query the Fenwick Tree for counts of smaller values, then update the tree with the current prefix. This transforms the problem into an inversion-style counting task.

This technique combines prefix sum transformations with efficient frequency queries using a Fenwick Tree. The same idea appears in advanced range-counting problems involving arrays and can also be implemented with divide-and-conquer techniques similar to segment tree or merge-sort based counting.

Recommended for interviews: Interviewers expect the prefix transformation plus Binary Indexed Tree approach. Starting with brute force shows understanding of the majority condition, but moving to prefix sums and Fenwick Tree demonstrates algorithmic maturity and knowledge of range counting techniques.