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.

Description Hints 5 Solution Video 6:05

1157. Online Majority Element In Subarray

Hard40.9% acceptance1 company

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 * 10⁴
1 <= arr[i] <= 2 * 10⁴
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
At most 10⁴ calls will be made to query.

Asked at 1 company

Nutanix

Topics

Hints open one at a time

Hint 1

What's special about a majority element ?

Hint 2

A majority element appears more than half the length of the array number of times.

Hint 3

If we tried a random index of the array, what's the probability that this index has a majority element ?

Hint 4

It's more than 50% if that array has a majority element.

Hint 5

Try a random index for a proper number of times so that the probability of not finding the answer tends to zero.

6:05

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class MajorityChecker:
2 
3    def __init__(self, arr: List[int]):
4        
5 
6    def query(self, left: int, right: int, threshold: int) -> int:
7        
8 
9 
10# Your MajorityChecker object will be instantiated and called as such:
11# obj = MajorityChecker(arr)
12# param_1 = obj.query(left,right,threshold)

Starter codePython 3Spaces: 4

Examples

Case 1

Input

["MajorityChecker","query","query","query"]
[[[1,1,2,2,1,1]],[0,5,4],[0,3,3],[2,3,2]]

Your code is saved on this device.Solution