Count Subarrays With Majority Element I - Solution & Explanation

Problem Overview: You are given an array and must count how many subarrays contain a majority element, meaning one value appears strictly more than half of the subarray length. The challenge is efficiently checking the majority condition across all possible subarrays.

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

The most direct strategy enumerates every subarray using two nested loops and then checks whether a majority element exists inside it. For each subarray [i, j], count frequencies of elements and verify whether any value occurs more than (j - i + 1) / 2 times. This requires scanning the subarray again to compute counts, resulting in O(n^3) time. It is straightforward and useful for understanding the majority definition but becomes impractical for large arrays.

Approach 2: Optimized Enumeration with Frequency Map (O(n^2) time, O(n) space)

A better solution still enumerates all subarrays but avoids recomputing frequencies from scratch. Fix the starting index i, then extend the right boundary j one step at a time. Maintain a running frequency map using a hash table and track the current maximum frequency. For each extension, update the count of nums[j], update the max frequency, and check whether maxFreq * 2 > (j - i + 1). This converts the inner work from scanning the entire subarray to constant-time updates, reducing total complexity to O(n^2). This approach is practical for medium input sizes and commonly appears in interview-style enumeration problems.

Approach 3: Prefix Balance Transformation (Conceptual Optimization)

For deeper optimization, the majority condition can be transformed using prefix balances. For a chosen candidate value, convert the array into +1 (candidate) and -1 (others). A subarray has that candidate as majority if its transformed sum is positive. Using techniques from prefix sum and counting valid prefix differences (sometimes with divide and conquer or merge-based counting), you can count qualifying segments more efficiently for each candidate. While more complex, this idea connects majority detection with classic prefix comparison problems.

Recommended for interviews: The optimized enumeration approach is the most practical answer. It demonstrates understanding of subarray enumeration, incremental frequency updates, and hash-based counting. Mentioning the brute force approach shows baseline reasoning, while the optimized O(n^2) solution proves you can reduce redundant work.