Formatted question description: https://leetcode.ca/all/1157.html

1157. Online Majority Element In Subarray

Level

Hard

Description

Implementing the class MajorityChecker, which has the following API:

  • MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
  • int query(int left, int right, int threshold) has arguments such that:
    • 0 <= left <= right < arr.length representing a subarray of arr;
    • 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right] that occurs at least threshold times, or -1 if no such element exists.

Example:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

Constraints:

  • 1 <= arr.length <= 20000
  • 1 <= arr[i] <= 20000
  • For each query, 0 <= left <= right < len(arr)
  • For each query, 2 * threshold > right - left + 1
  • The number of queries is at most 10000

Solution

Maintain an array in the class. For the constructor, simply assign the array to the array in the class. For method query, since the elements are in the range [1, 20000], create an array count of length 20001, and loop over the array from index left to index right. If at one point, a number’s count reaches threshold, then return the number. If no such number is met, return -1.

class MajorityChecker {
    int[] arr;

	public MajorityChecker(int[] arr) {
		this.arr = arr;
	}

	public int query(int left, int right, int threshold) {
		int[] count = new int[20001];
		for (int i = left; i <= right; i++) {
            int num = arr[i];
			if (++count[num] == threshold)
				return num;
		}
		return -1;
	}
}

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker obj = new MajorityChecker(arr);
 * int param_1 = obj.query(left,right,threshold);
 */

All Problems

All Solutions