Skip to main content
Talentd

Online Majority Element In Subarray - Solution & Explanation

HardArrayBinary SearchDesignBinary Indexed Tree17 min readAsked at: Nutanix
Practice this problem

Problem Statement

Design a data structure that efficiently finds the majority element of a given subarray.

The majority element of a subarray is an element that occurs threshold times or more in the subarray.

Implementing the MajorityChecker class:

  • MajorityChecker(int[] arr) Initializes the instance of the class with the given array arr.
  • int query(int left, int right, int threshold) returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.

 

Example 1:

Input
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
Output
[null, 1, -1, 2]

Explanation
MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]);
majorityChecker.query(0, 5, 4); // return 1
majorityChecker.query(0, 3, 3); // return -1
majorityChecker.query(2, 3, 2); // return 2

 

Constraints:

  • 1 <= arr.length <= 2 * 104
  • 1 <= arr[i] <= 2 * 104
  • 0 <= left <= right < arr.length
  • threshold <= right - left + 1
  • 2 * threshold > right - left + 1
  • At most 104 calls will be made to query.

Approach Overview

Problem Overview: You receive an integer array and many queries of the form (left, right, threshold). For each query, return the element that appears at least threshold times inside the subarray arr[left...right]. If no such element exists, return -1. Since queries are online and frequent, repeatedly scanning the subarray is too slow.

Approach 1: Hash Map with Preprocessing + Binary Search (Average O(log n) per query, O(n) space)

Preprocess the array using a hash map that stores a sorted list of indices for every distinct value. This allows you to count how many times a value appears inside any range using binary search. During a query, randomly sample a few indices from the range [left, right]. Each sampled value becomes a candidate majority. Use binary search on its index list to count occurrences inside the range and check whether it meets the threshold. Each verification takes O(log n), and sampling a small constant number of candidates keeps the expected query time close to O(log n). This approach relies on the probability that a true majority element will be sampled quickly.

The key idea is fast frequency verification. The hash map stores value → sorted indices, and binary search finds the first and last positions inside the query range. You avoid scanning the entire subarray while still confirming exact counts. This technique combines array preprocessing with binary search for efficient range counting.

Approach 2: Segment Tree with Majority Candidate (O(log n) query, O(n) space)

A more deterministic solution builds a segment tree. Each node stores a candidate element and a relative count using the Boyer–Moore majority merge idea. When combining two segments, if both candidates match, their counts add; otherwise the larger count survives after subtraction. This process propagates a potential majority candidate upward.

For a query range, the segment tree returns a candidate in O(log n). That candidate may not actually meet the threshold, so verify it using the same preprocessing map of value → sorted indices. Counting occurrences with binary search takes O(log n). The overall query cost becomes O(log n) with reliable worst‑case behavior.

This design separates two responsibilities: the segment tree quickly proposes a candidate, while the index map verifies its true frequency. The tree handles range queries efficiently, and binary search provides exact counts without scanning the array.

Recommended for interviews: Start by explaining why brute force O(n) per query is too slow when queries are large. Then move to the segment tree approach. Interviewers typically expect a range-query structure combined with frequency verification. The hash map preprocessing shows good practical optimization, while the segment tree demonstrates strong understanding of range data structures.

Approach 1: Hash Map with Preprocessing

Preprocess the input array to create a map that keeps count of the index positions for each element. Use this map to efficiently determine the count of an element in any given subarray, enabling quick queries for the majority element.

This solution uses a defaultdict to store the indices of each element in the array. When a query is made, it checks possible candidates based on the existing numbers in the subarray, and verifies their frequency using binary search to locate their positions quickly.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n log n) for preprocessing and O(k log m) for each query, where k is the number of unique elements in the subarray and m is their frequency. Space Complexity: O(n), where n is the length of the array due to storage of indices.

Try this approach in the editor →

Approach 2: Segment Tree with Lazy Propagation

Use a segment tree to preprocess the given array. Each node in the segment tree maintains information about the majority element in that segment along with its frequency. Lazy propagation is used to efficiently update ranges during queries.

Here, a segment tree is used to preprocess the array. Each node represents the majority element of that segment and its frequency relative to the segment. During query operations, the segment tree quickly retrieves and recombines results for subarrays, updating only the segments that require attention, thus utilizing lazy evaluation with a complexity close to logarithmic.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n) to build the segment tree and O(log n + k) for each query, where k is the number of operations merged. Space Complexity: O(n) due to extra storage for the segment tree.

Try this approach in the editor →

Approach 3: Segment Tree + Boyer-Moore Voting Algorithm + Binary Search

We notice that the problem requires us to find the possible majority element in a specific interval, so we consider using a segment tree to maintain the candidate majority element and its occurrence in each interval.

We define each node of the segment tree as Node, each node contains the following attributes:

  • l: The left endpoint of the node, the index starts from 1.
  • r: The right endpoint of the node, the index starts from 1.
  • x: The candidate majority element of the node.
  • cnt: The occurrence of the candidate majority element of the node.

The segment tree mainly has the following operations:

  • build(u, l, r): Build the segment tree.
  • pushup(u): Use the information of the child nodes to update the information of the parent node.
  • query(u, l, r): Query the interval sum.

In the initialization method of the main function, we first create a segment tree, and use a hash table d to record all indexes of each element in the array.

In the query(left, right, threshold) method, we directly call the query method of the segment tree to get the candidate majority element x. Then use binary search to find the first index l in the array that is greater than or equal to left, and the first index r that is greater than right. If r - l \ge threshold, return x, otherwise return -1.

In terms of time complexity, the time complexity of the initialization method is O(n), and the time complexity of the query method is O(log n). The space complexity is O(n). Here, n is the length of the array.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Hash Map with Preprocessing

Time Complexity: O(n log n) for preprocessing and O(k log m) for each query, where k is the number of unique elements in the subarray and m is their frequency. Space Complexity: O(n), where n is the length of the array due to storage of indices.

Segment Tree with Lazy Propagation

Time Complexity: O(n) to build the segment tree and O(log n + k) for each query, where k is the number of operations merged. Space Complexity: O(n) due to extra storage for the segment tree.

Segment Tree + Boyer-Moore Voting Algorithm + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Frequency CountO(n) per queryO(1)Small arrays or very few queries
Hash Map + Random Sampling + Binary SearchExpected O(log n) per queryO(n)Practical solution with fast average performance
Segment Tree with Majority CandidateO(log n) query, O(n) buildO(n)Deterministic approach for many range queries

Video Solution

Leetcode 1157. Online Majority Element In Subarray • coderZ • 1,145 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Online Majority Element In Subarray easy or hard?
Online Majority Element In Subarray is classified as a Hard problem on LeetCode. The difficulty comes from handling many online queries efficiently and combining multiple techniques such as preprocessing, segment trees, and binary search verification.
Online Majority Element In Subarray Python/Java solution
Python implementations often use a dictionary mapping values to sorted index lists plus random sampling and binary search for verification. Java and C++ solutions frequently combine the same index map with a segment tree that returns a majority candidate for each query.
How to solve Online Majority Element In Subarray in O(log n)?
Build a segment tree where each node stores a potential majority candidate using a Boyer–Moore style merge. For a query range, retrieve the candidate in O(log n). Then count its occurrences in the range using binary search on a preprocessed list of indices to verify whether it meets the threshold.
What is the best approach for Online Majority Element In Subarray?
The most reliable approach uses a segment tree to produce a potential majority candidate for a range and then verifies the candidate using a preprocessed index map with binary search. Each query runs in O(log n) time after O(n) preprocessing. This balances fast queries with guaranteed correctness.
Is Online Majority Element In Subarray asked at Google/Amazon/Meta?
Range query problems involving segment trees, frequency counting, and majority voting patterns appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. This problem tests both data structure design and query optimization.
What data structure is used in Online Majority Element In Subarray?
Common data structures include hash maps for preprocessing value positions, binary search for fast range counting, and segment trees for efficient range candidate queries. These structures allow queries to run in logarithmic time instead of scanning subarrays.
What is the time complexity of Online Majority Element In Subarray?
Efficient solutions answer each query in O(log n) time. Preprocessing the array and building supporting data structures such as an index map or segment tree takes O(n). Verification of a candidate majority typically uses binary search on stored indices.

Ready to solve this problem?

Practice Online Majority Element In Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays