Package g1101_1200.s1157_online_majority_element_in_subarray

Class MajorityChecker

java.lang.Object

g1101_1200.s1157_online_majority_element_in_subarray.MajorityChecker

public class MajorityChecker
extends Object

1157 - Online Majority Element In Subarray.<p>Hard</p> <p>Design a data structure that efficiently finds the <strong>majority element</strong> of a given subarray.</p> <p>The <strong>majority element</strong> of a subarray is an element that occurs <code>threshold</code> times or more in the subarray.</p> <p>Implementing the <code>MajorityChecker</code> class:</p> <ul> <li><code>MajorityChecker(int[] arr)</code> Initializes the instance of the class with the given array <code>arr</code>.</li> <li><code>int query(int left, int right, int threshold)</code> returns the element in the subarray <code>arr[left...right]</code> that occurs at least <code>threshold</code> times, or <code>-1</code> if no such element exists.</li> </ul> <p><strong>Example 1:</strong></p> <p><strong>Input</strong> [&ldquo;MajorityChecker&rdquo;, &ldquo;query&rdquo;, &ldquo;query&rdquo;, &ldquo;query&rdquo;] [<a href="1,-1,-2,-2,-1,-1">1, 1, 2, 2, 1, 1</a>, [0, 5, 4], [0, 3, 3], [2, 3, 2]]</p> <p><strong>Output:</strong> [null, 1, -1, 2]</p> <p><strong>Explanation:</strong></p> <p>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</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= arr.length <= 2 * 10⁴</code></li> <li><code>1 <= arr[i] <= 2 * 10⁴</code></li> <li><code>0 <= left <= right < arr.length</code></li> <li><code>threshold <= right - left + 1</code></li> <li><code>2 * threshold > right - left + 1</code></li> <li>At most <code>10⁴</code> calls will be made to <code>query</code>.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
MajorityChecker(int[] arr)

Method Summary

Modifier and Type	Method	Description
int	query(int left, int right, int threshold)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MajorityChecker

public MajorityChecker(int[] arr)

Method Details

query

public int query(int left,
 int right,
 int threshold)