#1157

Online Majority Element In Subarray

master · 1705 · lc hard +32 · 40.2% accepted · 662 likes · top 20%

Description

Create an efficient data structure for locating the dominant element within any queried subarray.

The dominant element of a subarray is any element that appears at least threshold times within it.

Implement the MajorityChecker class:

- MajorityChecker(int[] arr) constructs an instance using the provided array arr.

- int query(int left, int right, int threshold) returns the element in subarray arr[left...right] appearing at least threshold times, or -1 if none 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]

Example 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

Code

class MajorityChecker:

    def __init__(self, arr: List[int]):
        

    def query(self, left: int, right: int, threshold: int) -> int:
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

class MajorityChecker:

    def __init__(self, arr: List[int]):
        

    def query(self, left: int, right: int, threshold: int) -> int:
        


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)