Online Majority Element In Subarray

Problem Description

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. Implement the MajorityChecker class with the methods MajorityChecker(int[] arr) to initialize the instance with the given array arr, and int query(int left, int right, int threshold) to return the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.

Key Insights

• A majority element in a subarray is defined as an element that appears at least threshold times.
• Efficient querying is necessary due to the potential size of the array and the number of queries.
• The problem can leverage data structures like Segment Trees or Binary Indexed Trees for efficient range queries and updates.

Space and Time Complexity

Time Complexity: O(log n) for updates and O(k) for queries, where k is the number of unique elements in the queried range.
Space Complexity: O(n) for storing the data structures.

Solution

To solve the problem, we can use a combination of a HashMap (or dictionary) to count occurrences of elements in the queried range and a preprocessing step to facilitate fast queries. The MajorityChecker class will keep track of the counts of elements within segments of the array.

1. Initialization: Store the input array and prepare for efficient querying.
2. Query Method: For each query, count occurrences of each element in the subarray defined by the indices left and right. Check if any element meets the threshold criteria.
3. Optimized Counting: Utilize a HashMap to store counts of elements and check against the threshold.

Code Solutions