1157. Online Majority Element In Subarray
Problem Description
You need to design a data structure that can efficiently find the majority element within any given subarray of an array.
A majority element in a subarray is defined as an element that appears at least threshold
times in that subarray.
The MajorityChecker
class should support the following operations:
-
Constructor
MajorityChecker(int[] arr)
: Initialize the data structure with the given arrayarr
. -
Query Method
int query(int left, int right, int threshold)
:- Find an element in the subarray
arr[left...right]
(inclusive) that occurs at leastthreshold
times - Return that element if it exists
- Return
-1
if no such element exists
- Find an element in the subarray
For example, if you have an array [1, 1, 2, 2, 1, 1]
and you query the subarray from index 0 to 5 with threshold 4, the method should return 1
since it appears 4 times in that range. If you query the subarray from index 2 to 3 with threshold 2, it should return 2
since it appears 2 times in that range.
The challenge is to handle multiple queries efficiently after the initial array is provided, making this a problem that requires preprocessing and clever data structure design rather than a naive approach of counting elements for each query.
Intuition
When we need to find a majority element in a subarray that appears at least threshold
times, a naive approach would be to count every element in the range for each query, which would be inefficient for multiple queries.
The key insight comes from the Boyer-Moore Voting Algorithm, which can find a candidate majority element in linear time. This algorithm works by maintaining a candidate element and a counter - when we see the same element, we increment the counter, and when we see a different element, we decrement it. The element that survives is a potential majority element.
But how do we apply this to arbitrary subarrays efficiently? This is where the Segment Tree comes in. We can build a segment tree where each node stores:
- A candidate majority element for that segment
- A "net count" representing how dominant that element is
When merging two segments, we apply Boyer-Moore logic:
- If both segments have the same candidate, we add their counts
- If they have different candidates, the one with the higher count "wins" and we subtract the smaller count from the larger
This gives us a potential majority element for any range in O(log n)
time. However, the Boyer-Moore algorithm only gives us a candidate - it might not actually be the majority element with the required threshold.
To verify if this candidate actually appears threshold
times, we need to count its actual occurrences in the range. This is where binary search comes in. By preprocessing and storing all positions where each element appears (in sorted order), we can use binary search to quickly find how many times the candidate appears in our query range:
- Find the leftmost position
>= left
- Find the rightmost position
<= right
- The difference gives us the actual count
This combination of segment tree (for finding candidates), Boyer-Moore voting (for merging segments), and binary search (for verification) gives us an efficient solution that handles queries in O(log n)
time after O(n log n)
preprocessing.
Learn more about Segment Tree and Binary Search patterns.
Solution Approach
The solution implements three main components: a Segment Tree with Boyer-Moore voting logic, preprocessing of element positions, and binary search for verification.
1. Segment Tree Implementation
The Node
class represents each node in the segment tree with:
l, r
: Left and right boundaries of the segment (1-indexed)x
: The candidate majority element for this segmentcnt
: The net count of the candidate element
The SegmentTree
class builds the tree in the constructor:
build(u, l, r)
: Recursively builds the tree- For leaf nodes (when
l == r
), sets the element value and count to 1 - For internal nodes, builds left and right children, then merges using
pushup
- For leaf nodes (when
2. Boyer-Moore Voting Logic in pushup
The pushup(u)
method merges information from child nodes using Boyer-Moore logic:
- If both children have the same candidate element
x
:- Parent's candidate =
x
- Parent's count = sum of both counts
- Parent's candidate =
- If children have different candidates:
- Parent's candidate = element with higher count
- Parent's count = difference between the counts (higher - lower)
This maintains the Boyer-Moore invariant: the surviving element with its net count represents the potential majority element.
3. Query Operation in Segment Tree
The query(u, l, r)
method retrieves the candidate for any range:
- If current node's range is completely within query range, return its
(x, cnt)
- If query range is entirely in left or right half, recurse to that child
- If query spans both children:
- Get candidates from both sides
- Merge them using Boyer-Moore logic (same as
pushup
)
4. Main Class Implementation
The MajorityChecker
class combines everything:
Initialization:
- Creates the segment tree from the input array
- Builds a dictionary
d
whered[x]
contains all indices where elementx
appears (sorted)
Query Method:
- Call segment tree's
query(1, left + 1, right + 1)
to get candidatex
- Note: Adding 1 because segment tree uses 1-based indexing
- Use binary search to verify the candidate:
bisect_left(d[x], left)
: Find first occurrence ofx
at or afterleft
bisect_left(d[x], right + 1)
: Find first occurrence ofx
afterright
- The difference
r - l
gives the actual count ofx
in the range
- Return
x
if count>= threshold
, otherwise return-1
Time Complexity
- Preprocessing:
O(n log n)
to build the segment tree andO(n)
to build the position dictionary - Query:
O(log n)
for segment tree query +O(log n)
for two binary searches =O(log n)
total
Space Complexity
O(n)
for the segment tree (4n nodes)O(n)
for the position dictionary- Total:
O(n)
This approach efficiently handles multiple queries by preprocessing the data structure once and then answering each query in logarithmic time.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through the solution with array [2, 2, 1, 3, 1, 1, 1, 3]
and query (2, 6, 2)
(find majority element in indices 2-6 with threshold 2).
Step 1: Build Segment Tree
The segment tree builds recursively with Boyer-Moore voting at each node:
Tree structure (showing [candidate, count]): [1,1] (covers indices 1-8) / \ [2,1] (1-4) [1,3] (5-8) / \ / \ [2,2] (1-2) [1,1] (3-4) [1,2] (5-6) [1,1] (7-8) / \ / \ / \ / \ [2,1] [2,1] [1,1] [3,1] [1,1] [1,1] [1,1] [3,1] (1) (2) (3) (4) (5) (6) (7) (8)
Notice how node (1-4) merges its children:
- Left child has [2,2] (element 2 with count 2)
- Right child has [1,1] (element 1 with count 1, and 3 with count 1 cancels out)
- Since candidates differ: winner is 2 with count 2-1=1, so node stores [2,1]
Step 2: Build Position Dictionary
Create a map of each element to its positions:
d = { 2: [0, 1], 1: [2, 4, 5, 6], 3: [3, 7] }
Step 3: Query (2, 6, 2)
Convert to 1-based indexing: query segment tree for range (3, 7).
The segment tree query traverses:
- Start at root [1,1] covering (1-8)
- Query range (3-7) spans both children, so query both:
- Left child (1-4): Only positions 3-4 needed, returns [1,1]
- Right child (5-8): Only positions 5-7 needed, returns [1,3]
- Merge results using Boyer-Moore:
- Both have candidate 1
- Combined count: 1 + 3 = 4
- Return candidate [1,4]
Step 4: Verify Candidate
Check if element 1 actually appears ≥2 times in original range [2,6]:
positions = d[1] = [2, 4, 5, 6] left_idx = bisect_left([2, 4, 5, 6], 2) = 0 # First position ≥ 2 right_idx = bisect_left([2, 4, 5, 6], 7) = 4 # First position > 6 count = 4 - 0 = 4
Since count (4) ≥ threshold (2), return 1.
Another Query Example: (0, 2, 3)
- Query segment tree for range (1, 3):
- Returns candidate [2,1] (element 2 with net count 1)
- Verify element 2:
positions = d[2] = [0, 1] left_idx = bisect_left([0, 1], 0) = 0 right_idx = bisect_left([0, 1], 3) = 2 count = 2 - 0 = 2
- Since count (2) < threshold (3), return -1.
This example demonstrates how the segment tree efficiently finds candidates using Boyer-Moore voting, and binary search verifies the actual count.
Solution Implementation
1from typing import List
2from collections import defaultdict
3from bisect import bisect_left
4
5
6class Node:
7 """Node for segment tree storing potential majority element and its count."""
8 __slots__ = ("left", "right", "candidate", "count")
9
10 def __init__(self):
11 self.left = 0 # Left boundary of segment
12 self.right = 0 # Right boundary of segment
13 self.candidate = 0 # Potential majority element in this segment
14 self.count = 0 # Net count of candidate (using Boyer-Moore logic)
15
16
17class SegmentTree:
18 """
19 Segment tree that maintains potential majority elements using Boyer-Moore voting.
20 Each node stores a candidate element and its net count after cancellation.
21 """
22
23 def __init__(self, nums: List[int]):
24 self.nums = nums
25 n = len(nums)
26 # Allocate 4n nodes for the segment tree (standard practice)
27 self.nodes = [Node() for _ in range(n << 2)]
28 self.build(1, 1, n)
29
30 def build(self, node_idx: int, left: int, right: int) -> None:
31 """Build the segment tree recursively."""
32 self.nodes[node_idx].left = left
33 self.nodes[node_idx].right = right
34
35 # Base case: leaf node
36 if left == right:
37 self.nodes[node_idx].candidate = self.nums[left - 1] # 1-indexed to 0-indexed
38 self.nodes[node_idx].count = 1
39 return
40
41 # Recursive case: build left and right children
42 mid = (left + right) >> 1
43 left_child = node_idx << 1
44 right_child = (node_idx << 1) | 1
45
46 self.build(left_child, left, mid)
47 self.build(right_child, mid + 1, right)
48
49 # Update current node based on children
50 self._push_up(node_idx)
51
52 def query(self, node_idx: int, query_left: int, query_right: int) -> tuple[int, int]:
53 """
54 Query the potential majority element in range [query_left, query_right].
55 Returns (candidate, net_count) using Boyer-Moore voting logic.
56 """
57 current_node = self.nodes[node_idx]
58
59 # Case 1: Current segment is fully within query range
60 if current_node.left >= query_left and current_node.right <= query_right:
61 return current_node.candidate, current_node.count
62
63 mid = (current_node.left + current_node.right) >> 1
64 left_child = node_idx << 1
65 right_child = (node_idx << 1) | 1
66
67 # Case 2: Query range is entirely in left subtree
68 if query_right <= mid:
69 return self.query(left_child, query_left, query_right)
70
71 # Case 3: Query range is entirely in right subtree
72 if query_left > mid:
73 return self.query(right_child, query_left, query_right)
74
75 # Case 4: Query range spans both subtrees - merge results
76 left_candidate, left_count = self.query(left_child, query_left, query_right)
77 right_candidate, right_count = self.query(right_child, query_left, query_right)
78
79 # Apply Boyer-Moore voting logic to merge
80 if left_candidate == right_candidate:
81 return left_candidate, left_count + right_count
82 elif left_count >= right_count:
83 return left_candidate, left_count - right_count
84 else:
85 return right_candidate, right_count - left_count
86
87 def _push_up(self, node_idx: int) -> None:
88 """
89 Update parent node based on its children using Boyer-Moore voting.
90 This merges two segments' majority candidates.
91 """
92 left_child = node_idx << 1
93 right_child = (node_idx << 1) | 1
94
95 left_node = self.nodes[left_child]
96 right_node = self.nodes[right_child]
97 current_node = self.nodes[node_idx]
98
99 # If both children have same candidate, add their counts
100 if left_node.candidate == right_node.candidate:
101 current_node.candidate = left_node.candidate
102 current_node.count = left_node.count + right_node.count
103 # Otherwise, the one with higher count survives (with reduced count)
104 elif left_node.count >= right_node.count:
105 current_node.candidate = left_node.candidate
106 current_node.count = left_node.count - right_node.count
107 else:
108 current_node.candidate = right_node.candidate
109 current_node.count = right_node.count - left_node.count
110
111
112class MajorityChecker:
113 """
114 Data structure to efficiently check if an element appears >= threshold times
115 in any subarray. Uses segment tree to find potential majority candidates.
116 """
117
118 def __init__(self, arr: List[int]):
119 # Build segment tree for finding potential majority elements
120 self.tree = SegmentTree(arr)
121
122 # Store positions of each element for verification
123 self.element_positions = defaultdict(list)
124 for index, value in enumerate(arr):
125 self.element_positions[value].append(index)
126
127 def query(self, left: int, right: int, threshold: int) -> int:
128 """
129 Check if any element appears >= threshold times in arr[left:right+1].
130 Returns the element if found, otherwise -1.
131 """
132 # Get potential majority candidate from segment tree (1-indexed query)
133 candidate, _ = self.tree.query(1, left + 1, right + 1)
134
135 # Verify if candidate actually appears >= threshold times
136 # Binary search to count occurrences of candidate in range
137 positions = self.element_positions[candidate]
138 left_bound = bisect_left(positions, left)
139 right_bound = bisect_left(positions, right + 1)
140
141 actual_count = right_bound - left_bound
142 return candidate if actual_count >= threshold else -1
143
144
145# Your MajorityChecker object will be instantiated and called as such:
146# obj = MajorityChecker(arr)
147# param_1 = obj.query(left,right,threshold)
148
1/**
2 * Node class representing a segment in the segment tree
3 */
4class Node {
5 int left, right; // Range boundaries [left, right]
6 int candidate, count; // Majority element candidate and its count difference
7}
8
9/**
10 * Segment Tree implementation for finding majority element candidates
11 * Uses Boyer-Moore voting algorithm concept in tree structure
12 */
13class SegmentTree {
14 private Node[] tree;
15 private int[] numbers;
16
17 /**
18 * Constructor to build the segment tree
19 * @param nums Input array
20 */
21 public SegmentTree(int[] nums) {
22 int n = nums.length;
23 this.numbers = nums;
24 // Allocate 4 times the array size for the tree
25 tree = new Node[n << 2];
26 for (int i = 0; i < tree.length; ++i) {
27 tree[i] = new Node();
28 }
29 // Build tree with 1-indexed positions
30 build(1, 1, n);
31 }
32
33 /**
34 * Recursively build the segment tree
35 * @param nodeIndex Current node index in the tree
36 * @param left Left boundary of the range
37 * @param right Right boundary of the range
38 */
39 private void build(int nodeIndex, int left, int right) {
40 tree[nodeIndex].left = left;
41 tree[nodeIndex].right = right;
42
43 // Leaf node: single element
44 if (left == right) {
45 tree[nodeIndex].candidate = numbers[left - 1]; // Convert to 0-indexed
46 tree[nodeIndex].count = 1;
47 return;
48 }
49
50 int mid = (left + right) >> 1;
51 // Build left subtree
52 build(nodeIndex << 1, left, mid);
53 // Build right subtree
54 build(nodeIndex << 1 | 1, mid + 1, right);
55 // Merge results from children
56 pushup(nodeIndex);
57 }
58
59 /**
60 * Query the segment tree for majority candidate in range [left, right]
61 * @param nodeIndex Current node index
62 * @param queryLeft Left boundary of query range
63 * @param queryRight Right boundary of query range
64 * @return Array containing [candidate, count]
65 */
66 public int[] query(int nodeIndex, int queryLeft, int queryRight) {
67 // Current node completely within query range
68 if (tree[nodeIndex].left >= queryLeft && tree[nodeIndex].right <= queryRight) {
69 return new int[] {tree[nodeIndex].candidate, tree[nodeIndex].count};
70 }
71
72 int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
73
74 // Query range completely in left subtree
75 if (queryRight <= mid) {
76 return query(nodeIndex << 1, queryLeft, queryRight);
77 }
78
79 // Query range completely in right subtree
80 if (queryLeft > mid) {
81 return query(nodeIndex << 1 | 1, queryLeft, queryRight);
82 }
83
84 // Query range spans both subtrees - merge results
85 int[] leftResult = query(nodeIndex << 1, queryLeft, queryRight);
86 int[] rightResult = query(nodeIndex << 1 | 1, queryLeft, queryRight);
87
88 // Apply Boyer-Moore voting algorithm logic
89 if (leftResult[0] == rightResult[0]) {
90 // Same candidate: add counts
91 leftResult[1] += rightResult[1];
92 } else if (leftResult[1] >= rightResult[1]) {
93 // Left candidate dominates: subtract right count
94 leftResult[1] -= rightResult[1];
95 } else {
96 // Right candidate dominates: subtract left count
97 rightResult[1] -= leftResult[1];
98 leftResult = rightResult;
99 }
100
101 return leftResult;
102 }
103
104 /**
105 * Update parent node based on children nodes (Boyer-Moore voting merge)
106 * @param nodeIndex Current node index
107 */
108 private void pushup(int nodeIndex) {
109 int leftChild = nodeIndex << 1;
110 int rightChild = nodeIndex << 1 | 1;
111
112 if (tree[leftChild].candidate == tree[rightChild].candidate) {
113 // Same candidate in both children: add counts
114 tree[nodeIndex].candidate = tree[leftChild].candidate;
115 tree[nodeIndex].count = tree[leftChild].count + tree[rightChild].count;
116 } else if (tree[leftChild].count >= tree[rightChild].count) {
117 // Left candidate dominates
118 tree[nodeIndex].candidate = tree[leftChild].candidate;
119 tree[nodeIndex].count = tree[leftChild].count - tree[rightChild].count;
120 } else {
121 // Right candidate dominates
122 tree[nodeIndex].candidate = tree[rightChild].candidate;
123 tree[nodeIndex].count = tree[rightChild].count - tree[leftChild].count;
124 }
125 }
126}
127
128/**
129 * MajorityChecker class to find majority elements in subarrays
130 */
131class MajorityChecker {
132 private SegmentTree segmentTree;
133 // Map to store indices for each value in the array
134 private Map<Integer, List<Integer>> valueToIndices = new HashMap<>();
135
136 /**
137 * Constructor to initialize the data structures
138 * @param arr Input array
139 */
140 public MajorityChecker(int[] arr) {
141 segmentTree = new SegmentTree(arr);
142
143 // Build index map for each value
144 for (int i = 0; i < arr.length; ++i) {
145 valueToIndices.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
146 }
147 }
148
149 /**
150 * Query for majority element in range [left, right] with given threshold
151 * @param left Left boundary (0-indexed)
152 * @param right Right boundary (0-indexed)
153 * @param threshold Minimum occurrences required
154 * @return Majority element if exists, otherwise -1
155 */
156 public int query(int left, int right, int threshold) {
157 // Get majority candidate from segment tree (convert to 1-indexed)
158 int candidate = segmentTree.query(1, left + 1, right + 1)[0];
159
160 // Verify the candidate by counting actual occurrences
161 List<Integer> indices = valueToIndices.get(candidate);
162 int leftIndex = binarySearch(indices, left);
163 int rightIndex = binarySearch(indices, right + 1);
164
165 // Check if candidate appears enough times
166 return (rightIndex - leftIndex) >= threshold ? candidate : -1;
167 }
168
169 /**
170 * Binary search to find the first index >= target
171 * @param indices Sorted list of indices
172 * @param target Target value to search for
173 * @return Index of first element >= target
174 */
175 private int binarySearch(List<Integer> indices, int target) {
176 int left = 0, right = indices.size();
177
178 while (left < right) {
179 int mid = (left + right) >> 1;
180 if (indices.get(mid) >= target) {
181 right = mid;
182 } else {
183 left = mid + 1;
184 }
185 }
186
187 return left;
188 }
189}
190
191/**
192 * Your MajorityChecker object will be instantiated and called as such:
193 * MajorityChecker obj = new MajorityChecker(arr);
194 * int param_1 = obj.query(left,right,threshold);
195 */
196
1class Node {
2public:
3 int left = 0, right = 0; // Range boundaries [left, right]
4 int value = 0, count = 0; // Majority element value and its net count
5};
6
7using pii = pair<int, int>;
8
9class SegmentTree {
10public:
11 SegmentTree(vector<int>& nums) {
12 this->nums = nums;
13 int n = nums.size();
14 nodes.resize(n << 2); // Allocate 4n nodes for the segment tree
15 for (int i = 0; i < nodes.size(); ++i) {
16 nodes[i] = new Node();
17 }
18 build(1, 1, n); // Build tree with 1-based indexing
19 }
20
21 // Query the majority element in range [l, r]
22 // Returns {majority_value, net_count} using Moore's Voting Algorithm
23 pii query(int nodeIdx, int queryLeft, int queryRight) {
24 // If current node's range is completely within query range
25 if (nodes[nodeIdx]->left >= queryLeft && nodes[nodeIdx]->right <= queryRight) {
26 return {nodes[nodeIdx]->value, nodes[nodeIdx]->count};
27 }
28
29 int mid = (nodes[nodeIdx]->left + nodes[nodeIdx]->right) >> 1;
30
31 // Query is entirely in left subtree
32 if (queryRight <= mid) {
33 return query(nodeIdx << 1, queryLeft, queryRight);
34 }
35
36 // Query is entirely in right subtree
37 if (queryLeft > mid) {
38 return query(nodeIdx << 1 | 1, queryLeft, queryRight);
39 }
40
41 // Query spans both subtrees - merge results using Moore's algorithm
42 auto leftResult = query(nodeIdx << 1, queryLeft, queryRight);
43 auto rightResult = query(nodeIdx << 1 | 1, queryLeft, queryRight);
44
45 // Merge two segments' majority elements
46 if (leftResult.first == rightResult.first) {
47 // Same majority element - add counts
48 leftResult.second += rightResult.second;
49 } else if (leftResult.second >= rightResult.second) {
50 // Left majority survives - subtract right count
51 leftResult.second -= rightResult.second;
52 } else {
53 // Right majority survives - subtract left count
54 rightResult.second -= leftResult.second;
55 leftResult = rightResult;
56 }
57 return leftResult;
58 }
59
60private:
61 vector<Node*> nodes; // Segment tree nodes
62 vector<int> nums; // Original array
63
64 // Build segment tree recursively
65 void build(int nodeIdx, int rangeLeft, int rangeRight) {
66 nodes[nodeIdx]->left = rangeLeft;
67 nodes[nodeIdx]->right = rangeRight;
68
69 // Leaf node - single element
70 if (rangeLeft == rangeRight) {
71 nodes[nodeIdx]->value = nums[rangeLeft - 1]; // Convert to 0-based index
72 nodes[nodeIdx]->count = 1;
73 return;
74 }
75
76 // Build left and right subtrees
77 int mid = (rangeLeft + rangeRight) >> 1;
78 build(nodeIdx << 1, rangeLeft, mid);
79 build(nodeIdx << 1 | 1, mid + 1, rangeRight);
80
81 // Update current node based on children
82 pushUp(nodeIdx);
83 }
84
85 // Update parent node based on its children using Moore's Voting Algorithm
86 void pushUp(int nodeIdx) {
87 int leftChild = nodeIdx << 1;
88 int rightChild = nodeIdx << 1 | 1;
89
90 if (nodes[leftChild]->value == nodes[rightChild]->value) {
91 // Same majority element in both children
92 nodes[nodeIdx]->value = nodes[leftChild]->value;
93 nodes[nodeIdx]->count = nodes[leftChild]->count + nodes[rightChild]->count;
94 } else if (nodes[leftChild]->count >= nodes[rightChild]->count) {
95 // Left child's majority element survives
96 nodes[nodeIdx]->value = nodes[leftChild]->value;
97 nodes[nodeIdx]->count = nodes[leftChild]->count - nodes[rightChild]->count;
98 } else {
99 // Right child's majority element survives
100 nodes[nodeIdx]->value = nodes[rightChild]->value;
101 nodes[nodeIdx]->count = nodes[rightChild]->count - nodes[leftChild]->count;
102 }
103 }
104};
105
106class MajorityChecker {
107public:
108 MajorityChecker(vector<int>& arr) {
109 segmentTree = new SegmentTree(arr);
110
111 // Build position map for each unique value
112 for (int i = 0; i < arr.size(); ++i) {
113 valuePositions[arr[i]].push_back(i);
114 }
115 }
116
117 // Query if there's a majority element in range [left, right] with frequency >= threshold
118 int query(int left, int right, int threshold) {
119 // Get potential majority element using segment tree
120 int candidateValue = segmentTree->query(1, left + 1, right + 1).first;
121
122 // Verify if candidate appears >= threshold times in the range
123 auto leftIter = lower_bound(valuePositions[candidateValue].begin(),
124 valuePositions[candidateValue].end(), left);
125 auto rightIter = lower_bound(valuePositions[candidateValue].begin(),
126 valuePositions[candidateValue].end(), right + 1);
127
128 // Count occurrences in range
129 int occurrences = rightIter - leftIter;
130 return occurrences >= threshold ? candidateValue : -1;
131 }
132
133private:
134 unordered_map<int, vector<int>> valuePositions; // Map from value to its positions
135 SegmentTree* segmentTree; // Segment tree for range majority queries
136};
137
138/**
139 * Your MajorityChecker object will be instantiated and called as such:
140 * MajorityChecker* obj = new MajorityChecker(arr);
141 * int param_1 = obj->query(left,right,threshold);
142 */
143
1// Node structure for segment tree
2interface Node {
3 left: number; // Range left boundary
4 right: number; // Range right boundary
5 value: number; // Majority element value in this range
6 count: number; // Net count of majority element (using Moore's algorithm)
7}
8
9// Global variables
10let nodes: Node[] = []; // Segment tree nodes array
11let nums: number[] = []; // Original input array
12let valuePositions: Map<number, number[]> = new Map(); // Map from value to its position indices
13
14/**
15 * Build segment tree recursively
16 * @param nodeIdx - Current node index in the tree
17 * @param rangeLeft - Left boundary of current range (1-based)
18 * @param rangeRight - Right boundary of current range (1-based)
19 */
20function build(nodeIdx: number, rangeLeft: number, rangeRight: number): void {
21 nodes[nodeIdx].left = rangeLeft;
22 nodes[nodeIdx].right = rangeRight;
23
24 // Base case: leaf node represents single element
25 if (rangeLeft === rangeRight) {
26 nodes[nodeIdx].value = nums[rangeLeft - 1]; // Convert to 0-based index
27 nodes[nodeIdx].count = 1;
28 return;
29 }
30
31 // Recursively build left and right subtrees
32 const mid = (rangeLeft + rangeRight) >> 1;
33 build(nodeIdx << 1, rangeLeft, mid);
34 build((nodeIdx << 1) | 1, mid + 1, rangeRight);
35
36 // Update current node based on children
37 pushUp(nodeIdx);
38}
39
40/**
41 * Update parent node based on its children using Moore's Voting Algorithm
42 * @param nodeIdx - Current node index to update
43 */
44function pushUp(nodeIdx: number): void {
45 const leftChild = nodeIdx << 1;
46 const rightChild = (nodeIdx << 1) | 1;
47
48 if (nodes[leftChild].value === nodes[rightChild].value) {
49 // Same majority element in both children - add counts
50 nodes[nodeIdx].value = nodes[leftChild].value;
51 nodes[nodeIdx].count = nodes[leftChild].count + nodes[rightChild].count;
52 } else if (nodes[leftChild].count >= nodes[rightChild].count) {
53 // Left child's majority element survives
54 nodes[nodeIdx].value = nodes[leftChild].value;
55 nodes[nodeIdx].count = nodes[leftChild].count - nodes[rightChild].count;
56 } else {
57 // Right child's majority element survives
58 nodes[nodeIdx].value = nodes[rightChild].value;
59 nodes[nodeIdx].count = nodes[rightChild].count - nodes[leftChild].count;
60 }
61}
62
63/**
64 * Query the potential majority element in range [queryLeft, queryRight]
65 * @param nodeIdx - Current node index in traversal
66 * @param queryLeft - Left boundary of query range (1-based)
67 * @param queryRight - Right boundary of query range (1-based)
68 * @returns [majority_value, net_count] pair
69 */
70function querySegmentTree(nodeIdx: number, queryLeft: number, queryRight: number): [number, number] {
71 // Current node's range is completely within query range
72 if (nodes[nodeIdx].left >= queryLeft && nodes[nodeIdx].right <= queryRight) {
73 return [nodes[nodeIdx].value, nodes[nodeIdx].count];
74 }
75
76 const mid = (nodes[nodeIdx].left + nodes[nodeIdx].right) >> 1;
77
78 // Query is entirely in left subtree
79 if (queryRight <= mid) {
80 return querySegmentTree(nodeIdx << 1, queryLeft, queryRight);
81 }
82
83 // Query is entirely in right subtree
84 if (queryLeft > mid) {
85 return querySegmentTree((nodeIdx << 1) | 1, queryLeft, queryRight);
86 }
87
88 // Query spans both subtrees - merge results using Moore's algorithm
89 let leftResult = querySegmentTree(nodeIdx << 1, queryLeft, queryRight);
90 const rightResult = querySegmentTree((nodeIdx << 1) | 1, queryLeft, queryRight);
91
92 // Merge two segments' majority elements
93 if (leftResult[0] === rightResult[0]) {
94 // Same majority element - add counts
95 leftResult[1] += rightResult[1];
96 } else if (leftResult[1] >= rightResult[1]) {
97 // Left majority survives - subtract right count
98 leftResult[1] -= rightResult[1];
99 } else {
100 // Right majority survives - subtract left count
101 leftResult = [rightResult[0], rightResult[1] - leftResult[1]];
102 }
103
104 return leftResult;
105}
106
107/**
108 * Binary search to find the first position >= target
109 * @param positions - Sorted array of positions
110 * @param target - Target value to search for
111 * @returns Index of first element >= target
112 */
113function lowerBound(positions: number[], target: number): number {
114 let left = 0;
115 let right = positions.length;
116
117 while (left < right) {
118 const mid = (left + right) >> 1;
119 if (positions[mid] < target) {
120 left = mid + 1;
121 } else {
122 right = mid;
123 }
124 }
125
126 return left;
127}
128
129/**
130 * Initialize the MajorityChecker with given array
131 * @param arr - Input array
132 */
133function MajorityChecker(arr: number[]): void {
134 nums = arr;
135 const n = arr.length;
136
137 // Initialize segment tree nodes (4n nodes for safety)
138 nodes = new Array(n << 2);
139 for (let i = 0; i < nodes.length; i++) {
140 nodes[i] = { left: 0, right: 0, value: 0, count: 0 };
141 }
142
143 // Build segment tree with 1-based indexing
144 build(1, 1, n);
145
146 // Build position map for each unique value
147 valuePositions = new Map();
148 for (let i = 0; i < arr.length; i++) {
149 if (!valuePositions.has(arr[i])) {
150 valuePositions.set(arr[i], []);
151 }
152 valuePositions.get(arr[i])!.push(i);
153 }
154}
155
156/**
157 * Query if there's a majority element in range [left, right] with frequency >= threshold
158 * @param left - Left boundary of query range (0-based)
159 * @param right - Right boundary of query range (0-based)
160 * @param threshold - Minimum frequency required
161 * @returns The majority element if exists and meets threshold, otherwise -1
162 */
163function query(left: number, right: number, threshold: number): number {
164 // Get potential majority element using segment tree (convert to 1-based indexing)
165 const candidateValue = querySegmentTree(1, left + 1, right + 1)[0];
166
167 // Get all positions where candidate value appears
168 const positions = valuePositions.get(candidateValue) || [];
169
170 // Find occurrences in range [left, right] using binary search
171 const leftIndex = lowerBound(positions, left);
172 const rightIndex = lowerBound(positions, right + 1);
173
174 // Count occurrences in the specified range
175 const occurrences = rightIndex - leftIndex;
176
177 // Return candidate if it meets threshold, otherwise -1
178 return occurrences >= threshold ? candidateValue : -1;
179}
180
Time and Space Complexity
Time Complexity:
-
Initialization (
__init__
):O(n log n)
- Building the segment tree takes
O(n)
time as each node is visited once during the build process - Creating the dictionary
d
with position lists requires iterating through the array once, which isO(n)
- However, if we consider that each element might need to be appended to a list (which could involve resizing), the worst case remains
O(n)
- But actually, the reference answer states
O(n)
, which is correct as the segment tree build isO(n)
and dictionary creation isO(n)
, giving totalO(n)
- Building the segment tree takes
-
Query (
query
):O(log n)
- The segment tree query operation traverses at most
O(log n)
nodes from root to leaf - The binary search operations (
bisect_left
) on the position list also takeO(log n)
time - Total query complexity is
O(log n) + O(log n) = O(log n)
- The segment tree query operation traverses at most
Space Complexity: O(n)
- The segment tree uses
4n
nodes (allocated asn << 2
), which isO(n)
space - The dictionary
d
stores the positions of all elements, usingO(n)
space in total (each index appears exactly once across all lists) - Each
Node
object has a fixed number of attributes due to__slots__
, maintaining constant space per node - Total space complexity is
O(n) + O(n) = O(n)
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Misunderstanding Boyer-Moore Voting Algorithm Limitations
Pitfall: The Boyer-Moore voting algorithm only guarantees finding an element that appears more than n/2 times if such an element exists. It doesn't guarantee finding elements that appear frequently but less than n/2 times. Many developers mistakenly believe the candidate returned by the segment tree is always the answer.
Example of the issue:
# Array: [1, 2, 3, 1, 1] # Query: left=0, right=4, threshold=3 # Boyer-Moore might return 1 as candidate (correct in this case) # But for Array: [1, 2, 3, 4, 5, 1, 1] # Query: left=0, right=6, threshold=3 # Boyer-Moore might not return 1 as the candidate
Solution: Always verify the candidate by counting its actual occurrences using the position dictionary and binary search. Never skip the verification step:
def query(self, left: int, right: int, threshold: int) -> int:
candidate, _ = self.tree.query(1, left + 1, right + 1)
# CRITICAL: Must verify the candidate
positions = self.element_positions[candidate]
left_bound = bisect_left(positions, left)
right_bound = bisect_left(positions, right + 1)
actual_count = right_bound - left_bound
# Only return if verified
return candidate if actual_count >= threshold else -1
2. Index Conversion Errors Between 0-based and 1-based
Pitfall: The segment tree uses 1-based indexing internally while the input array and query parameters use 0-based indexing. Mixing these up causes incorrect range queries.
Common mistakes:
# WRONG: Forgetting to convert indices
def query(self, left: int, right: int, threshold: int) -> int:
candidate, _ = self.tree.query(1, left, right) # Bug!
# WRONG: Converting in the wrong place
def build(self, node_idx: int, left: int, right: int) -> None:
if left == right:
# Should be [left - 1], not [left]
self.nodes[node_idx].candidate = self.nums[left] # Bug!
Solution: Consistently handle index conversion at interface boundaries:
def query(self, left: int, right: int, threshold: int) -> int:
# Convert 0-based to 1-based when calling segment tree
candidate, _ = self.tree.query(1, left + 1, right + 1)
def build(self, node_idx: int, left: int, right: int) -> None:
if left == right:
# Convert 1-based segment tree index to 0-based array index
self.nodes[node_idx].candidate = self.nums[left - 1]
3. Incorrect Binary Search Boundary for Counting Occurrences
Pitfall: Using the wrong boundary in binary search when counting occurrences in a range, especially forgetting that bisect_left
finds the insertion point, not necessarily an existing element.
Common mistake:
# WRONG: Using right instead of right + 1 right_bound = bisect_left(positions, right) # Bug! Misses element at index 'right' # WRONG: Using bisect_right for left boundary left_bound = bisect_right(positions, left) # Bug! May skip valid occurrences
Solution: Use bisect_left
correctly for both boundaries:
# Find first position >= left left_bound = bisect_left(positions, left) # Find first position > right (equivalent to >= right + 1) right_bound = bisect_left(positions, right + 1) # Count = number of positions in [left, right] actual_count = right_bound - left_bound
4. Memory Allocation for Segment Tree
Pitfall: Allocating insufficient memory for the segment tree. A common mistake is allocating exactly 2n nodes, which isn't enough for all cases.
Wrong approach:
# WRONG: Not enough nodes
self.nodes = [Node() for _ in range(n * 2)] # Bug!
Solution: Always allocate 4n nodes for a segment tree to handle worst-case scenarios:
# Correct: 4n nodes ensures enough space
self.nodes = [Node() for _ in range(n << 2)] # n * 4
5. Handling Edge Cases with Empty Results
Pitfall: Not handling the case where no element meets the threshold requirement, or assuming the Boyer-Moore candidate always exists.
Solution: Always return -1 when no valid element is found:
def query(self, left: int, right: int, threshold: int) -> int:
candidate, _ = self.tree.query(1, left + 1, right + 1)
# Handle case where candidate might not exist in element_positions
if candidate not in self.element_positions:
return -1
positions = self.element_positions[candidate]
left_bound = bisect_left(positions, left)
right_bound = bisect_left(positions, right + 1)
actual_count = right_bound - left_bound
# Explicitly return -1 if threshold not met
return candidate if actual_count >= threshold else -1
Which data structure is used to implement recursion?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!