Introduction

The classic majority-element problem asks whether some value appears more than half the time in an array. The harder variant asks the same question for parts of an array, such as a subrange from index l to r. That change matters because the best algorithm for one whole-array answer is not automatically the best algorithm for many range queries.

Whole Array Versus Subarray Queries

For the whole array, the standard solution is Boyer-Moore voting. It finds a candidate in linear time with constant extra space, then verifies the candidate with a second pass.

1def majority_element(nums):
2    candidate = None
3    count = 0
4
5    for value in nums:
6        if count == 0:
7            candidate = value
8            count = 1
9        elif value == candidate:
10            count += 1
11        else:
12            count -= 1
13
14    if candidate is None:
15        return None
16
17    frequency = sum(1 for value in nums if value == candidate)
18    return candidate if frequency > len(nums) // 2 else None
19
20
21print(majority_element([2, 2, 1, 1, 2, 2, 2]))

That works beautifully for one global answer. It does not solve repeated range queries efficiently because you would have to rerun the logic on each subarray.

Why Subranges Need Preprocessing

Suppose the same array is queried thousands of times:

• majority in indices 0 through 10
• majority in indices 5 through 40
• majority in indices 100 through 200

Brute-force counting on every query is simple but can become too slow. For many queries, it is worth preprocessing the array.

A practical exact strategy is:

1. build a structure that can return a candidate for a range
2. verify that candidate's true frequency in that range

The second step is essential. Candidate retrieval alone can produce a value that is not actually a majority in that particular interval.

Segment Tree for Candidates

A segment tree can store majority-style candidates using Boyer-Moore merge logic. Each node holds a pair of values: a candidate and a relative count.

1from bisect import bisect_left, bisect_right
2from collections import defaultdict
3
4
5class MajorityQuery:
6    def __init__(self, nums):
7        self.nums = nums
8        self.size = 1
9        while self.size < len(nums):
10            self.size *= 2
11
12        self.tree = [(None, 0)] * (2 * self.size)
13        for i, value in enumerate(nums):
14            self.tree[self.size + i] = (value, 1)
15
16        for i in range(self.size - 1, 0, -1):
17            self.tree[i] = self._merge(self.tree[2 * i], self.tree[2 * i + 1])
18
19        self.positions = defaultdict(list)
20        for i, value in enumerate(nums):
21            self.positions[value].append(i)
22
23    def _merge(self, left, right):
24        lv, lc = left
25        rv, rc = right
26
27        if lv is None:
28            return right
29        if rv is None:
30            return left
31        if lv == rv:
32            return (lv, lc + rc)
33        if lc > rc:
34            return (lv, lc - rc)
35        if rc > lc:
36            return (rv, rc - lc)
37        return (None, 0)
38
39    def _candidate(self, left, right):
40        left += self.size
41        right += self.size
42        result_left = (None, 0)
43        result_right = (None, 0)
44
45        while left <= right:
46            if left % 2 == 1:
47                result_left = self._merge(result_left, self.tree[left])
48                left += 1
49            if right % 2 == 0:
50                result_right = self._merge(self.tree[right], result_right)
51                right -= 1
52            left //= 2
53            right //= 2
54
55        return self._merge(result_left, result_right)[0]
56
57    def query(self, left, right):
58        candidate = self._candidate(left, right)
59        if candidate is None:
60            return None
61
62        idx = self.positions[candidate]
63        count = bisect_right(idx, right) - bisect_left(idx, left)
64        length = right - left + 1
65        return candidate if count > length // 2 else None
66
67
68mq = MajorityQuery([1, 2, 2, 3, 2, 2, 4, 2])
69print(mq.query(1, 5))
70print(mq.query(0, 3))

This gives fast range candidates and exact verification.

Why Verification Still Matters

The segment tree merge logic preserves a plausible candidate, not a proof. A range candidate must still be counted.

That is why the position lists are useful. For each distinct value, store the sorted indices where it appears. Then use binary search to count how many times it falls inside the query range.

This count step converts a plausible answer into a correct answer.

Complexity Tradeoffs

If you only need one answer for one array, use Boyer-Moore.

If you need many subrange majority queries:

• preprocessing costs more up front
• queries become much faster
• exact verification keeps correctness intact

This is the typical tradeoff in range-query problems. The right design depends on how many queries you expect.

When a Simpler Method Is Enough

If the array is small or there are only a few queries, a brute-force solution may be better because it is shorter and less error-prone.

1from collections import Counter
2
3
4def majority_in_range(nums, left, right):
5    sub = nums[left:right + 1]
6    counts = Counter(sub)
7    for value, count in counts.items():
8        if count > len(sub) // 2:
9            return value
10    return None

That is not optimal for large workloads, but it is perfectly reasonable when performance requirements are modest.

Common Pitfalls

One common mistake is treating the candidate returned by a segment-tree merge as automatically correct. It still has to be verified.

Another mistake is using greater-than-or-equal-to half instead of strictly greater than half. Majority means more than half, not at least half.

Developers also often introduce off-by-one errors in the binary-search verification step, especially around inclusive right bounds.

Finally, not every problem needs heavy preprocessing. If query volume is small, brute force may be the better engineering choice.

Summary

• Boyer-Moore is excellent for finding a majority element in the whole array.
• Subrange majority queries are a different problem and usually need preprocessing.
• A segment tree can provide range candidates efficiently.
• Candidate answers still need exact frequency verification.
• Choose preprocessing only when the number of queries justifies the extra complexity.