3737. Count Subarrays With Majority Element I

MediumSegment TreeArrayHash TableDivide and ConquerCountingPrefix SumMerge Sort

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums and an integer target.

Your task is to return the number of subarrays of nums in which target is the majority element.

A subarray is a contiguous, non-empty sequence of elements within an array.

The majority element of a subarray is the element that appears strictly more than half of the times in that subarray. In other words, for a subarray of length k, an element is the majority element if it appears more than k / 2 times.

So, for each possible subarray, you need to check whether target occurs strictly more than half the length of that subarray. If it does, then target is the majority element of that subarray, and it should be counted toward the final answer.

For example, in a subarray of length 5, target must appear at least 3 times (since 3 > 5 / 2) to be considered the majority element. In a subarray of length 4, target must appear at least 3 times (since it must be strictly more than 2).

Return the total count of such subarrays where target is the majority element.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Maintaining frequency counts as each subarray window extends lets the majority condition cnt[target] > k/2 be checked in O(1) per subarray.

Open in Flowchart

Intuition

The most direct way to approach this problem is to think about what we actually need to count: every subarray where target appears strictly more than half the time. Since a subarray is defined by its starting and ending positions, a natural idea is to simply examine every possible subarray and check the condition for each one.

To do this, we can fix the starting position i of a subarray, and then gradually extend the ending position j from i to the end of the array. As we extend j one element at a time, the subarray nums[i..j] grows by exactly one element. This means we don't need to recount everything from scratch each time — we can maintain a running count of how many times each element has appeared in the current subarray.

The key observation is that as we extend j, we only add the new element nums[j] to our count. So we use a hash table cnt to track the frequency of each value in the current subarray. After adding nums[j], the length of the subarray is k = j - i + 1. To decide whether target is the majority element, we just check if cnt[target] > k // 2. If this holds, then target appears strictly more than half the time, and we increment our answer.

By resetting the count whenever we start a new starting position i, and incrementally updating it as j moves forward, we can efficiently evaluate the majority condition for all subarrays. This leads us naturally to a straightforward enumeration over all (i, j) pairs.

Pattern Learn more about Segment Tree, Divide and Conquer, Prefix Sum and Merge Sort patterns.

Solution Approach

We solve this problem using Enumeration combined with a hash table to track element frequencies.

The idea is to enumerate every possible subarray and directly check whether target is its majority element. We do this with two nested loops:

Outer loop — fix the starting position i: We iterate i over the range [0, n-1], where n is the length of nums. Each value of i marks the beginning of a group of subarrays that all start at index i.
Initialize a fresh hash table cnt: For each starting position i, we create a new counter cnt (using Counter). This hash table records how many times each element appears in the current subarray. Resetting it for every i ensures the counts only reflect the subarray starting at i.
Inner loop — extend the ending position j: We iterate j over the range [i, n-1]. For each j, the current subarray is nums[i..j], and its length is k = j - i + 1. Since the subarray grows by exactly one element each step, we only need to add the new element to our count:
- Update the frequency: cnt[nums[j]] += 1.
Check the majority condition: After updating the count, we determine whether target is the majority element of nums[i..j]. The majority condition requires target to appear strictly more than half the time, which translates to:
- cnt[target] > k // 2
Here, k // 2 is integer division. For a subarray of length k, an element must appear more than k // 2 times to be the strict majority (for example, length 4 requires more than 2, i.e. at least 3 times; length 5 requires more than 2, i.e. at least 3 times). If this condition holds, we increment ans by 1.
Return the answer: After both loops complete, ans holds the total number of subarrays in which target is the majority element, and we return it.

Complexity Analysis:

Time complexity: O(n^2), since we enumerate all O(n^2) subarrays, and updating the count and checking the condition for each takes O(1) time on average.
Space complexity: O(n), due to the hash table cnt, which in the worst case stores up to n distinct elements for a given starting position.

Example Walkthrough

Let's trace through the solution approach with a small example.

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

We want to count all subarrays where 1 appears strictly more than half the time. We fix each starting index i, reset our counter cnt, then extend j to the right while checking the majority condition cnt[target] > k // 2.

Starting position i = 0 (reset cnt = {})

`j`	element added	subarray	`cnt`	`k`	`k // 2`	`cnt[1]`	`cnt[1] > k//2`?	`ans`
0	`1`	`[1]`	`{1:1}`	1	0	1	`1 > 0` ✅	1
1	`2`	`[1,2]`	`{1:1, 2:1}`	2	1	1	`1 > 1` ❌	1
2	`1`	`[1,2,1]`	`{1:2, 2:1}`	3	1	2	`2 > 1` ✅	2
3	`3`	`[1,2,1,3]`	`{1:2, 2:1, 3:1}`	4	2	2	`2 > 2` ❌	2

Starting position i = 1 (reset cnt = {})

`j`	element added	subarray	`cnt`	`k`	`k // 2`	`cnt[1]`	`cnt[1] > k//2`?	`ans`
1	`2`	`[2]`	`{2:1}`	1	0	0	`0 > 0` ❌	2
2	`1`	`[2,1]`	`{2:1, 1:1}`	2	1	1	`1 > 1` ❌	2
3	`3`	`[2,1,3]`	`{2:1, 1:1, 3:1}`	3	1	1	`1 > 1` ❌	2

Starting position i = 2 (reset cnt = {})

`j`	element added	subarray	`cnt`	`k`	`k // 2`	`cnt[1]`	`cnt[1] > k//2`?	`ans`
2	`1`	`[1]`	`{1:1}`	1	0	1	`1 > 0` ✅	3
3	`3`	`[1,3]`	`{1:1, 3:1}`	2	1	1	`1 > 1` ❌	3

Starting position i = 3 (reset cnt = {})

`j`	element added	subarray	`cnt`	`k`	`k // 2`	`cnt[1]`	`cnt[1] > k//2`?	`ans`
3	`3`	`[3]`	`{3:1}`	1	0	0	`0 > 0` ❌	3

Result: The qualifying subarrays are [1] (at index 0), [1,2,1] (indices 0–2), and [1] (at index 2). The final answer is ans = 3.

This walkthrough shows how the counter is reset for each new starting index i, incrementally updated by adding only nums[j] as j extends, and how the check cnt[target] > k // 2 correctly identifies the strict majority for each of the O(n^2) subarrays.

Solution Implementation

1from typing import List
2from collections import Counter
3
4
5class Solution:
6    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
7        # Total number of elements in the input array
8        length = len(nums)
9        # Stores the count of subarrays where `target` is the majority element
10        result = 0
11
12        # Fix the left boundary of the subarray at index `left`
13        for left in range(length):
14            # Frequency counter for elements in the current subarray
15            counter = Counter()
16
17            # Extend the right boundary from `left` to the end of the array
18            for right in range(left, length):
19                # Current subarray length: nums[left..right]
20                window_size = right - left + 1
21                # Include the newly added element in the frequency count
22                counter[nums[right]] += 1
23
24                # `target` is the majority if it appears more than half the time
25                if counter[target] > window_size // 2:
26                    result += 1
27
28        return result
29

1class Solution {
2    public int countMajoritySubarrays(int[] nums, int target) {
3        // Length of the input array
4        int length = nums.length;
5
6        // Counter for subarrays where target is the majority element
7        int answer = 0;
8
9        // Map to track the frequency of each value within the current subarray window
10        Map<Integer, Integer> frequencyMap = new HashMap<>(length);
11
12        // Fix the left boundary of the subarray at index 'start'
13        for (int start = 0; start < length; ++start) {
14            // Extend the right boundary of the subarray to index 'end'
15            for (int end = start; end < length; ++end) {
16                // Current length of the subarray [start, end]
17                int subarrayLength = end - start + 1;
18
19                // Add the current element to the frequency map
20                frequencyMap.merge(nums[end], 1, Integer::sum);
21
22                // A "majority" element must appear more than half the times.
23                // If the target's count exceeds subarrayLength / 2, count this subarray.
24                if (frequencyMap.getOrDefault(target, 0) > subarrayLength / 2) {
25                    ++answer;
26                }
27            }
28            // Reset the frequency map before moving the left boundary forward
29            frequencyMap.clear();
30        }
31
32        return answer;
33    }
34}
35

1class Solution {
2public:
3    int countMajoritySubarrays(vector<int>& nums, int target) {
4        int n = nums.size();
5        int ans = 0;
6
7        // Fix the left endpoint of the subarray at index 'left'
8        for (int left = 0; left < n; ++left) {
9            // Count occurrences of each value in the current subarray
10            unordered_map<int, int> count;
11
12            // Extend the subarray to the right, ending at index 'right'
13            for (int right = left; right < n; ++right) {
14                // Current subarray length is nums[left..right]
15                int length = right - left + 1;
16
17                // Include the new rightmost element in the frequency count
18                count[nums[right]]++;
19
20                // 'target' is the majority element if it appears strictly
21                // more than half the time in the subarray
22                if (count[target] > length / 2) {
23                    ++ans;
24                }
25            }
26        }
27
28        return ans;
29    }
30};
31

1/**
2 * Counts the number of subarrays where the target value appears
3 * more than half of the time (i.e., it is the strict majority element).
4 *
5 * @param nums - The input array of numbers.
6 * @param target - The value to check for majority occurrence.
7 * @returns The total count of subarrays where target is the majority element.
8 */
9function countMajoritySubarrays(nums: number[], target: number): number {
10    const length = nums.length;
11    let answer = 0;
12
13    // Iterate over every possible starting index of a subarray.
14    for (let start = 0; start < length; ++start) {
15        // Track the frequency of each value within the current subarray.
16        const frequency: Record<number, number> = {};
17
18        // Extend the subarray to every possible ending index.
19        for (let end = start; end < length; ++end) {
20            // Current length of the subarray [start, end].
21            const subarrayLength = end - start + 1;
22
23            // Increment the count for the value at the current end index.
24            frequency[nums[end]] = (frequency[nums[end]] || 0) + 1;
25
26            // Check if target appears more than half the subarray length.
27            // (subarrayLength >> 1) is equivalent to Math.floor(subarrayLength / 2).
28            if ((frequency[target] || 0) > subarrayLength >> 1) {
29                ++answer;
30            }
31        }
32    }
33
34    return answer;
35}
36

Time and Space Complexity

Time Complexity: O(n^2), where n is the length of the array nums. The outer loop iterates n times with index i, and for each i, the inner loop iterates from i to n - 1. The total number of (i, j) pairs is n + (n - 1) + ... + 1 = n * (n + 1) / 2, which is O(n^2). The operations inside the inner loop (updating the counter and comparing counts) take O(1) time, so the overall time complexity is O(n^2).
Space Complexity: O(n), where n is the length of the array nums. The Counter object cnt is recreated in each iteration of the outer loop and, in the worst case (when all elements in a subarray are distinct), it can store up to O(n) distinct keys. Therefore, the extra space used is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misinterpreting the Majority Condition (Off-by-One Error)

The most common mistake is confusing "strictly more than half" with "at least half." The majority element must appear strictly more than k / 2 times, not k / 2 or more. This distinction is critical for even-length subarrays.

For example, in a subarray of length 4:

A correct check requires target to appear at least 3 times (since 3 > 2).
An incorrect check might accept 2 occurrences, treating exactly half as a majority — which is wrong.

Incorrect code:

# WRONG: accepts elements that appear exactly half the time
if counter[target] >= window_size / 2:
    result += 1

Why it fails: For window_size = 4, window_size / 2 == 2.0, so a count of 2 would incorrectly pass. Also, using / (float division) instead of // introduces floating-point comparison issues.

Solution: Use integer division with a strict > comparison. The condition counter[target] > window_size // 2 correctly handles both parities:

Length 4: window_size // 2 == 2, so we need > 2, i.e. at least 3. ✓
Length 5: window_size // 2 == 2, so we need > 2, i.e. at least 3. ✓

# CORRECT
if counter[target] > window_size // 2:
    result += 1

Pitfall 2: Forgetting to Reset the Counter for Each Starting Index

Another frequent error is declaring the counter outside the outer loop, or reusing it across different starting positions. The counter must reflect only the elements of the current subarray, so it has to be reset whenever the left boundary moves.

Incorrect code:

counter = Counter()          # declared once, never reset
for left in range(length):
    for right in range(left, length):
        counter[nums[right]] += 1   # counts leak from previous `left` values
        ...

Why it fails: Once left advances, the counter still holds frequencies from previous subarrays, inflating counter[target] and producing wrong results.

Solution: Initialize a fresh Counter() at the top of the outer loop (as done in the reference code), so each starting index begins counting from scratch.

Pitfall 3: Overlooking Performance Constraints

This O(n²) enumeration is simple but may time out when n is large (e.g. n ≥ 10^5).

Solution — Prefix-Sum / Balance Technique (O(n log n) or O(n)):

Transform each element: assign +1 if it equals target and -1 otherwise. Then target is the majority of nums[i..j] iff the sum of transformed values over [i, j] is positive (more +1s than -1s).

Define a prefix balance pre[k]. A subarray [i, j] qualifies when:

pre[j+1] - pre[i] > 0   →   pre[i] < pre[j+1]

So for each right endpoint, we count how many earlier prefix values are strictly less than the current one. This "count of smaller elements seen so far" can be computed efficiently with a Binary Indexed Tree (Fenwick Tree) or by merge-sort counting of inversions.

from typing import List
from sortedcontainers import SortedList

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        result = 0
        prefix = 0
        seen = SortedList([0])   # prefix sums encountered so far (start with pre[0]=0)

        for x in nums:
            prefix += 1 if x == target else -1
            # count of earlier prefixes strictly less than current `prefix`
            result += seen.bisect_left(prefix)
            seen.add(prefix)

        return result

Complexity: O(n log n) time, O(n) space — a major improvement that scales to large inputs while producing identical results.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering