3739. Count Subarrays With Majority Element II

HardSegment TreeArrayHash TableDivide and ConquerPrefix SumMerge Sort

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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

Return the number of subarrays of nums in which target is the majority element.

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 len, target is the majority element if the number of times target appears within that subarray is strictly greater than len / 2.

Key points to understand:

A subarray is a contiguous, non-empty portion of the array.
You need to count how many such subarrays exist where target dominates by appearing more than half the time.
Different subarrays (different start or end positions) are counted separately, even if they contain the same values.

Example walkthrough:

Suppose nums = [1, 2, 3, 2, 2] and target = 2. Consider the subarray [2, 2] (the last two elements). It has length 2, and target = 2 appears 2 times. Since 2 > 2 / 2 = 1, target is the majority element here, so this subarray counts.

Now consider the subarray [2, 3, 2]. It has length 3, and target = 2 appears 2 times. Since 2 > 3 / 2 = 1.5, target is the majority element, so this subarray counts as well.

However, a subarray like [1, 2] has length 2 with target = 2 appearing only 1 time. Since 1 is not strictly greater than 2 / 2 = 1, target is not the majority element, so this subarray does not count.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Prefix Sums?

This problem maps to Prefix Sums through a short path in the full flowchart.

Mapping target to +1 and others to -1 reduces majority counting to prefix-sum imbalances, with a segment tree for range updates.

Open in Flowchart

Intuition

The first challenge is the phrase "strictly more than half." Counting occurrences directly for every possible subarray would be too slow, so we need a smarter way to express this condition.

The key observation is a transformation trick: since we only care whether each element equals target or not, we can convert the array into +1 and -1 values:

If an element equals target, treat it as +1.
If an element does not equal target, treat it as -1.

Why does this help? In a subarray of length len, suppose target appears k times. Then the non-target elements appear len - k times. The sum of the transformed subarray becomes:

k * (+1) + (len - k) * (-1) = 2k - len

The condition "target is the majority element" means k > len / 2, which is the same as 2k > len, or 2k - len > 0. So target being the majority is exactly equivalent to the transformed subarray having a sum strictly greater than 0.

Now the problem becomes: count the number of subarrays whose sum is strictly greater than 0. This is a classic problem that can be solved with prefix sums.

Let s[i] denote the prefix sum of the first i transformed elements (with s[0] = 0). A subarray from index j+1 to i has sum s[i] - s[j]. We want this to be greater than 0, meaning s[i] - s[j] > 0, or equivalently s[j] < s[i].

So for each ending position i, we need to know how many earlier prefix sums s[j] are strictly less than the current prefix sum s[i]. If we add up this count over all positions, we get the final answer.

To count "how many previous values are less than the current value" efficiently as we scan through the array, we use a Binary Indexed Tree (Fenwick Tree). It lets us insert prefix sums and query how many of them are below a given value, each in O(log n) time.

One small detail: prefix sums can range from -n to n (negative values are possible). Since a Binary Indexed Tree only works with positive indices, we shift every prefix sum by n + 1, mapping the range [-n, n] into [1, 2n + 1]. This way every value safely fits into the tree's index space. We start by inserting the shifted value of the initial prefix sum s[0] = 0 (which becomes n + 1), and then process each element while updating and querying the tree.

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

Solution Approach

We use a Binary Indexed Tree (Fenwick Tree) combined with the prefix sum idea described above.

Step 1: Build the Binary Indexed Tree

The prefix sums range from -n to n, and after shifting by n + 1, the values fall into the range [1, 2n + 1]. So we create a Binary Indexed Tree of size 2n + 1:

tree = BinaryIndexedTree(n * 2 + 1)

The tree supports two operations:

update(x, delta): add delta to the count at position x, and propagate upward using x += x & -x.
query(x): return the total count from position 1 to x, by accumulating downward using x -= x & -x.

Both operations run in O(log n) time.

Step 2: Initialize the Starting Prefix Sum

We let s represent the current running prefix sum (already shifted). Initially, before processing any element, the prefix sum is 0, which after shifting by n + 1 becomes:

s = n + 1
tree.update(s, 1)

This records that the prefix sum 0 has occurred once.

Step 3: Scan the Array

We iterate through each element x in nums and update the prefix sum based on the +1 / -1 transformation:

s += 1 if x == target else -1

After updating, s represents the prefix sum at the current ending position (in shifted form).

Step 4: Count Valid Subarrays Ending Here

For the current position, we want subarrays whose sum is strictly greater than 0. As derived earlier, this means counting earlier prefix sums s[j] that are strictly less than the current s. In shifted terms, that is all recorded values in the range [1, s - 1]:

ans += tree.query(s - 1)

The query(s - 1) returns how many previously inserted prefix sums are strictly less than s, which is exactly the number of valid subarrays ending at the current position.

Step 5: Record the Current Prefix Sum

After counting, we insert the current prefix sum into the tree so it can be used by future positions:

tree.update(s, 1)

Step 6: Return the Answer

Once all elements are processed, ans holds the total number of subarrays in which target is the majority element:

return ans

Complexity Analysis

Time Complexity: O(n log n), since we process each of the n elements once, and each update and query operation on the Binary Indexed Tree takes O(log n) time.
Space Complexity: O(n), for the Binary Indexed Tree which stores up to 2n + 1 entries.

Example Walkthrough

Let's trace through a small example to see the solution approach in action.

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

Setup:

n = 3, so the Binary Indexed Tree has size 2n + 1 = 7.
The shift amount is n + 1 = 4, mapping prefix sums from [-3, 3] to [1, 7].
Initialize s = 4 (shifted value of prefix sum 0) and tree.update(4, 1).
The tree now records that prefix sum 0 has appeared once. ans = 0.

Transformation reminder: element == target becomes +1, otherwise -1. So [1, 2, 2] transforms to [-1, +1, +1].

Step i = 0, element x = 1:

x != target, so s += -1 → s = 3 (this is the shifted prefix sum after the first element; the true prefix sum is -1).
Count: tree.query(s - 1) = tree.query(2). We ask: how many recorded prefix sums are strictly less than 3? Only the value 4 is recorded, and 4 is not less than 3. So the query returns 0. ans += 0 → ans = 0.
Record: tree.update(3, 1). Tree now holds prefix sums {4: 1, 3: 1}.

Step i = 1, element x = 2:

x == target, so s += 1 → s = 4 (true prefix sum is 0).
Count: tree.query(3). How many recorded prefix sums are strictly less than 4? The recorded values are 4 and 3; only 3 is less than 4. So the query returns 1. ans += 1 → ans = 1.
- This corresponds to the subarray [2] (just the element at index 1), where target appears once in a length-1 subarray — clearly the majority.
Record: tree.update(4, 1). Tree now holds {4: 2, 3: 1}.

Step i = 2, element x = 2:

x == target, so s += 1 → s = 5 (true prefix sum is 1).
Count: tree.query(4). How many recorded prefix sums are strictly less than 5? Recorded values are 4 (count 2) and 3 (count 1), all less than 5. So the query returns 3. ans += 3 → ans = 4.
- These correspond to three subarrays ending at index 2:
  - [2] (index 2 alone) — majority.
  - [2, 2] (indices 1–2) — 2 appears twice in length 2, 2 > 1, majority.
  - [1, 2, 2] (indices 0–2) — 2 appears twice in length 3, 2 > 1.5, majority.
Record: tree.update(5, 1). Tree now holds {5: 1, 4: 2, 3: 1}.

Result: ans = 4.

Let's verify by listing every qualifying subarray directly:

Subarray	Length	Count of `2`	Majority?
`[2]` (index 1)	1	1	✅ `1 > 0.5`
`[2]` (index 2)	1	1	✅ `1 > 0.5`
`[2, 2]` (1–2)	2	2	✅ `2 > 1`
`[1, 2, 2]` (0–2)	3	2	✅ `2 > 1.5`

That's exactly 4 subarrays, matching our computed answer. Each time we processed an element, the Fenwick Tree query gave us the count of previous prefix sums smaller than the current one — which equals the number of valid subarrays ending at that position — and we accumulated those into ans.

Solution Implementation

1from typing import List
2
3
4class BinaryIndexedTree:
5    """A Fenwick Tree (Binary Indexed Tree) supporting point updates and prefix-sum queries."""
6
7    __slots__ = ("n", "c")
8
9    def __init__(self, n: int) -> None:
10        # n: the maximum index (size) of the tree.
11        self.n = n
12        # c: internal array holding partial sums; 1-indexed, so size is n + 1.
13        self.c = [0] * (n + 1)
14
15    def update(self, x: int, delta: int) -> None:
16        # Add `delta` to position `x`, then propagate to all responsible parents.
17        while x <= self.n:
18            self.c[x] += delta
19            x += x & -x  # move to the next index that includes position x.
20
21    def query(self, x: int) -> int:
22        # Return the prefix sum over [1, x].
23        s = 0
24        while x > 0:
25            s += self.c[x]
26            x -= x & -x  # move to the previous range that does not overlap.
27        return s
28
29
30class Solution:
31    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
32        # Count subarrays in which `target` is a strict majority element.
33        #
34        # Idea: map each element to +1 if it equals `target`, otherwise -1.
35        # A subarray (l, r] has `target` as a strict majority iff its mapped
36        # sum is positive, i.e. prefix[r] - prefix[l] > 0, equivalently
37        # prefix[l] < prefix[r].
38        #
39        # So for each prefix value we count how many earlier prefixes are
40        # strictly smaller, using a BIT for efficient counting.
41
42        n = len(nums)
43
44        # Prefix sums range from -n to n; shift by (n + 1) to keep indices
45        # within [1, 2n + 1] for the 1-indexed BIT.
46        tree = BinaryIndexedTree(n * 2 + 1)
47
48        # `s` is the running, shifted prefix sum. The empty prefix maps to n + 1.
49        s = n + 1
50        tree.update(s, 1)  # register the empty prefix.
51
52        ans = 0
53        for x in nums:
54            # Update the prefix sum: +1 when matching target, -1 otherwise.
55            s += 1 if x == target else -1
56            # Count earlier prefixes strictly smaller than the current one.
57            ans += tree.query(s - 1)
58            # Register the current prefix for future queries.
59            tree.update(s, 1)
60
61        return ans
62

1/**
2 * Binary Indexed Tree (Fenwick Tree) supporting point updates
3 * and prefix-sum queries in O(log n) time.
4 */
5class BinaryIndexedTree {
6    // Size of the value domain that the tree can index.
7    private int size;
8    // Internal storage array; index 0 is unused (1-based indexing).
9    private int[] tree;
10
11    /**
12     * Constructs a Binary Indexed Tree covering indices [1, size].
13     *
14     * @param size the maximum index the tree must support
15     */
16    public BinaryIndexedTree(int size) {
17        this.size = size;
18        this.tree = new int[size + 1];
19    }
20
21    /**
22     * Adds {@code delta} to the value stored at index {@code index}.
23     *
24     * @param index the 1-based position to update
25     * @param delta the amount to add at that position
26     */
27    public void update(int index, int delta) {
28        // Move upward through the tree, updating each responsible node.
29        for (; index <= size; index += index & -index) {
30            tree[index] += delta;
31        }
32    }
33
34    /**
35     * Computes the prefix sum over indices [1, index].
36     *
37     * @param index the 1-based upper bound of the query range
38     * @return the sum of all values from index 1 up to {@code index}
39     */
40    public int query(int index) {
41        int sum = 0;
42        // Walk downward, accumulating partial sums from each node.
43        for (; index > 0; index -= index & -index) {
44            sum += tree[index];
45        }
46        return sum;
47    }
48}
49
50class Solution {
51    /**
52     * Counts the number of subarrays in which {@code target} is the
53     * strict majority element (appears more than half the time).
54     *
55     * Idea: transform each element to +1 (equals target) or -1 (otherwise).
56     * A subarray (i, j] has target as majority exactly when its transformed
57     * sum is positive, i.e. prefix[j] > prefix[i]. For each prefix value we
58     * count how many earlier prefix values are strictly smaller using a BIT.
59     *
60     * @param nums   the input array
61     * @param target the value whose majority subarrays we are counting
62     * @return the total number of qualifying subarrays
63     */
64    public long countMajoritySubarrays(int[] nums, int target) {
65        int n = nums.length;
66
67        // Prefix sums range within [-n, n]; shift by (n + 1) to make them
68        // valid 1-based indices in the range [1, 2n + 1].
69        BinaryIndexedTree tree = new BinaryIndexedTree(2 * n + 1);
70
71        // Current shifted prefix sum, starting from the empty prefix (value 0).
72        int prefixSum = n + 1;
73
74        // Register the initial empty-prefix value in the tree.
75        tree.update(prefixSum, 1);
76
77        long ans = 0;
78        for (int x : nums) {
79            // Update the running prefix sum based on the transformation.
80            prefixSum += x == target ? 1 : -1;
81
82            // Count how many previous prefix sums are strictly smaller,
83            // i.e. lie in the range [1, prefixSum - 1].
84            ans += tree.query(prefixSum - 1);
85
86            // Record the current prefix sum for future queries.
87            tree.update(prefixSum, 1);
88        }
89        return ans;
90    }
91}
92

1class BinaryIndexedTree {
2private:
3    int size;            // Number of positions the tree can index
4    vector<int> tree;    // Internal storage for prefix-sum information
5
6public:
7    // Initialize a Fenwick tree (BIT) that supports indices from 1 to n
8    BinaryIndexedTree(int n)
9        : size(n)
10        , tree(n + 1, 0) {}
11
12    // Add 'delta' to position 'index', propagating to all responsible nodes
13    void update(int index, int delta) {
14        // Move upward by adding the lowest set bit each step
15        for (; index <= size; index += index & -index) {
16            tree[index] += delta;
17        }
18    }
19
20    // Return the prefix sum over the range [1, index]
21    int query(int index) {
22        int sum = 0;
23        // Move downward by removing the lowest set bit each step
24        for (; index > 0; index -= index & -index) {
25            sum += tree[index];
26        }
27        return sum;
28    }
29};
30
31class Solution {
32public:
33    long long countMajoritySubarrays(vector<int>& nums, int target) {
34        int n = nums.size();
35
36        // The prefix-sum value can range from -n to +n.
37        // Shift it by (n + 1) so all values map to positive BIT indices [1, 2n + 1].
38        BinaryIndexedTree tree(2 * n + 1);
39
40        // 'prefix' tracks: (count of target so far) - (count of non-target so far),
41        // offset by (n + 1) to keep it within valid BIT index bounds.
42        int prefix = n + 1;
43
44        // Record the initial empty-prefix state at the shifted zero point.
45        tree.update(prefix, 1);
46
47        long long ans = 0;
48        for (int x : nums) {
49            // Increment prefix when the element matches target, decrement otherwise.
50            // A subarray (l, r] has 'target' as the strict majority exactly when
51            // prefix[r] > prefix[l].
52            prefix += (x == target ? 1 : -1);
53
54            // Count earlier prefixes strictly smaller than the current one;
55            // each such prefix marks the start of a valid majority subarray.
56            ans += tree.query(prefix - 1);
57
58            // Register the current prefix value for future queries.
59            tree.update(prefix, 1);
60        }
61        return ans;
62    }
63};
64

1// Global state for the Binary Indexed Tree (Fenwick Tree)
2let treeSize: number; // Total size of the tree (number of valid indices)
3let treeArray: number[]; // 1-indexed array storing the tree's cumulative frequencies
4
5/**
6 * Initializes the Binary Indexed Tree with the given size.
7 * @param n - The number of indices the tree should support (1-indexed).
8 */
9function initTree(n: number): void {
10    treeSize = n;
11    treeArray = Array(n + 1).fill(0);
12}
13
14/**
15 * Adds `delta` to the value at position `x` and propagates the change upward.
16 * Uses the lowest set bit (x & -x) to move to the next responsible node.
17 * @param x - The 1-indexed position to update.
18 * @param delta - The value to add at position `x`.
19 */
20function update(x: number, delta: number): void {
21    for (; x <= treeSize; x += x & -x) {
22        treeArray[x] += delta;
23    }
24}
25
26/**
27 * Returns the prefix sum of values from index 1 to `x` (inclusive).
28 * Uses the lowest set bit (x & -x) to move to the previous responsible node.
29 * @param x - The 1-indexed upper bound of the query.
30 * @returns The cumulative sum over the range [1, x].
31 */
32function query(x: number): number {
33    let sum = 0;
34    for (; x > 0; x -= x & -x) {
35        sum += treeArray[x];
36    }
37    return sum;
38}
39
40/**
41 * Counts the number of subarrays in which `target` appears as a strict majority
42 * (i.e., more than half of the subarray's elements equal `target`).
43 *
44 * Strategy:
45 *   - Map each element to +1 if it equals `target`, otherwise -1.
46 *   - A subarray is "majority" exactly when its mapped-value sum is positive.
47 *   - Using prefix sums, a subarray (i, j] is majority when prefix[j] > prefix[i].
48 *   - For each prefix sum, count how many earlier prefix sums are strictly smaller.
49 *   - An offset (n + 1) keeps all prefix-sum indices within [1, 2n + 1] for the BIT.
50 *
51 * @param nums - The input array.
52 * @param target - The value whose majority occurrence is being counted.
53 * @returns The total number of majority subarrays.
54 */
55function countMajoritySubarrays(nums: number[], target: number): number {
56    const n = nums.length;
57
58    // The tree must index prefix sums shifted by (n + 1), spanning [1, 2n + 1].
59    initTree(2 * n + 1);
60
61    // Start prefix sum at the offset so values never go below 1.
62    let prefix = n + 1;
63
64    // Record the initial (empty-prefix) sum.
65    update(prefix, 1);
66
67    let ans = 0;
68    for (const x of nums) {
69        // Increase or decrease the running prefix sum based on the mapped value.
70        prefix += x === target ? 1 : -1;
71
72        // Count earlier prefix sums strictly less than the current one;
73        // each such prefix marks the start of a valid majority subarray.
74        ans += query(prefix - 1);
75
76        // Register the current prefix sum for future queries.
77        update(prefix, 1);
78    }
79
80    return ans;
81}
82

Time and Space Complexity

Time Complexity: O(n log n), where n is the length of the array nums.

The code iterates through each element of nums once, resulting in n iterations of the main loop.
Within each iteration, two operations are performed on the Binary Indexed Tree (BIT): tree.query(s - 1) and tree.update(s, 1).
Both the query and update operations of a Binary Indexed Tree run in O(log m) time, where m is the size of the tree. Here the tree size is 2n + 1, so each operation takes O(log(2n + 1)) = O(log n) time.
Therefore, the overall time complexity is n × O(log n) = O(n log n).

Space Complexity: O(n), where n is the length of the array nums.

The Binary Indexed Tree maintains an internal array c of size 2n + 2 (since it is initialized with n * 2 + 1 and uses n + 1 slots internally).
This array dominates the auxiliary space usage, which is proportional to n, giving a space complexity of O(n).

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

Common Pitfalls

Pitfall: Off-by-One Error in the Strict Inequality Query

The most common mistake in this solution is querying tree.query(s) instead of tree.query(s - 1).

Why this happens:

The condition for target being a strict majority is prefix[r] - prefix[l] > 0, which means prefix[l] < prefix[r] — a strict inequality. It's tempting to write tree.query(s) because we're "counting prefixes up to the current value," but query(s) includes prefixes that are equal to s (where the mapped subarray sum is exactly 0).

A subarray with sum 0 has target appearing exactly half the time, which is not strictly more than half. Including these would overcount.

Incorrect version:

ans += tree.query(s)  # WRONG: counts prefixes <= s, includes sum == 0 cases

Correct version:

ans += tree.query(s - 1)  # counts prefixes strictly less than s

Concrete example:

Take nums = [2, 1] and target = 2. The mapped array is [+1, -1].

Empty prefix: s = 0 (shifted), registered.
After 2: s = +1. The subarray [2] has sum 1 > 0, valid. query(s - 1) correctly returns 1.
After 1: s = 0. The subarray [2, 1] has sum 0, not valid.
- With query(s - 1): returns count of prefixes strictly < 0 → 0. ✓ Correct.
- With query(s): returns count of prefixes <= 0, which includes the empty prefix at 0 → 1. ✗ Wrongly counts [2, 1].

The correct answer is 1, but using query(s) would yield 2.

Secondary Pitfall: Incorrect Shift or Tree Sizing

Another subtle error is mis-sizing the BIT or choosing the wrong shift value.

Why this happens:

Prefix sums range from -n (all non-target) to +n (all target). To map these into the 1-indexed BIT domain [1, 2n + 1], the shift must be n + 1:

Minimum prefix -n → -n + (n + 1) = 1 ✓
Maximum prefix +n → n + (n + 1) = 2n + 1 ✓

Common mistakes:

s = n          # WRONG shift: -n maps to 0, which is invalid for a 1-indexed BIT
tree = BinaryIndexedTree(n * 2)  # WRONG size: max index 2n+1 exceeds the tree

If the shift is n instead of n + 1, the smallest prefix maps to index 0. Calling update(0, 1) enters an infinite loop because 0 & -0 == 0, so x never advances. Always verify both boundary cases map within [1, 2n + 1].

Correct setup:

s = n + 1
tree = BinaryIndexedTree(n * 2 + 1)

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:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering