‌

‌

‌

‌
‌

‌
‌

‌

‌
‌

‌
‌
‌
‌
‌
‌
‌
‌
‌
‌
‌
‌

‌
‌

‌

‌
‌
‌
‌
‌
‌

‌

‌
‌

‌
‌
‌
‌
‌
‌
‌
‌

‌
‌

‌
‌
‌
‌
‌
‌
‌
‌
‌
‌

Online Majority Element In Subarray - Practice Coding | SlaveCode

0

0123456789

0

0123456789

:

0

0123456789

0

0123456789

1157. Online Majority Element In Subarray

Hard

50 Points

Array

Binary Search

Design

Binary Indexed Tree

Segment Tree

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:

Examples

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.

1157. Online Majority Element In Subarray

Hard

50 Points

Array

Binary Search

Design

Binary Indexed Tree

Segment Tree

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:

Examples

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.