Facebook Pixel

1157. Online Majority Element In Subarray

HardDesignBinary Indexed TreeSegment TreeArrayBinary Search
Leetcode Link

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:

  1. Constructor MajorityChecker(int[] arr): Initialize the data structure with the given array arr.

  2. Query Method int query(int left, int right, int threshold):

    • Find an element in the subarray arr[left...right] (inclusive) that occurs at least threshold times
    • Return that element if it exists
    • Return -1 if no such element exists

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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 segment
  • cnt: 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

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
  • 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 where d[x] contains all indices where element x appears (sorted)

Query Method:

  1. Call segment tree's query(1, left + 1, right + 1) to get candidate x
    • Note: Adding 1 because segment tree uses 1-based indexing
  2. Use binary search to verify the candidate:
    • bisect_left(d[x], left): Find first occurrence of x at or after left
    • bisect_left(d[x], right + 1): Find first occurrence of x after right
    • The difference r - l gives the actual count of x in the range
  3. Return x if count >= threshold, otherwise return -1

Time Complexity

  • Preprocessing: O(n log n) to build the segment tree and O(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 Evaluator

Example 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:

  1. Start at root [1,1] covering (1-8)
  2. 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]
  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)

  1. Query segment tree for range (1, 3):
    • Returns candidate [2,1] (element 2 with net count 1)
  2. 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
  3. 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 is O(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 is O(n) and dictionary creation is O(n), giving total O(n)

  • 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 take O(log n) time
    • Total query complexity is O(log n) + O(log n) = O(log n)

Space Complexity: O(n)

  • The segment tree uses 4n nodes (allocated as n << 2), which is O(n) space
  • The dictionary d stores the positions of all elements, using O(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
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Recommended Readings

Segment Tree

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

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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!

Load More