Question - 8
Implementing the class MajorityChecker
, which has the following API:
MajorityChecker(int[] arr)
constructs an instance of MajorityChecker with the given arrayarr
;int query(int left, int right, int threshold)
has arguments such that:0 <= left <= right < arr.length
representing a subarray ofarr
;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
class MajorityChecker {
// A treeNode stores the majority element, with it's count
// for a given range
static class Pair {
int element, count;
Pair(int element, int count) {
this.element = element;
this.count = count;
}
}
int[] arr;
Pair[] tree;
// Map of Elements -> TreeSet of their indices
// This is used for finding the occourence of an element in a given range in O(logN)
Map<Integer, TreeSet<int[]>> map = new HashMap<>();
public MajorityChecker(int[] arr) {
this.arr = arr;
tree = new Pair[4 * arr.length];
for (int i = 0; i < arr.length; i++) {
map.computeIfAbsent(arr[i], k -> new TreeSet<>((a, b) -> a[0] - b[0]));
map.get(arr[i]).add(new int[] { i, map.get(arr[i]).size() });
}
// NlogN process
buildTree(0, arr.length - 1, 1);
}
public void buildTree(int start, int end, int index) {
if (start == end) {
tree[index] = new Pair(arr[start], 1);
return;
}
int mid = start + (end - start) / 2;
buildTree(start, mid, 2 * index);
buildTree(mid + 1, end, 2 * index + 1);
Pair left = tree[2 * index], right = tree[2 * index + 1];
int leftCount = 0, rightCount = 0;
if (left.element != -1)
leftCount = map.get(left.element).floor(new int[] { end, 0 })[1]
- map.get(left.element).ceiling(new int[] { start, 0 })[1] + 1;
if (right.element != -1)
rightCount = map.get(right.element).floor(new int[] { end, 0 })[1]
- map.get(right.element).ceiling(new int[] { start, 0 })[1] + 1;
if (leftCount * 2 > end - start + 1)
tree[index] = new Pair(left.element, leftCount);
else if (rightCount * 2 > end - start + 1)
tree[index] = new Pair(right.element, rightCount);
else
tree[index] = new Pair(-1, 0);
}
public int query(int left, int right, int threshold) {
// LogN*LogN
Pair majority = findMajority(0, arr.length - 1, 1, left, right);
if (majority.count >= threshold)
return majority.element;
return -1;
}
public Pair findMajority(int start, int end, int index, int L, int R) {
if (start > R || end < L)
return new Pair(-1, 0);
if (start >= L && end <= R)
return tree[index];
int mid = start + (end - start) / 2;
Pair left = findMajority(start, mid, 2 * index, L, R);
Pair right = findMajority(mid + 1, end, 2 * index + 1, L, R);
Pair ans = new Pair(-1, 0);
int leftCount = 0, rightCount = 0;
int limit1 = Math.max(L, start), limit2 = Math.min(R, end);
if (left.element != -1)
leftCount = map.get(left.element).floor(new int[] { limit2, 0 })[1]
- map.get(left.element).ceiling(new int[] { limit1, 0 })[1] + 1;
if (right.element != -1)
rightCount = map.get(right.element).floor(new int[] { limit2, 0 })[1]
- map.get(right.element).ceiling(new int[] { limit1, 0 })[1] + 1;
if (leftCount * 2 > limit2 - limit1 + 1)
ans = new Pair(left.element, leftCount);
else if (rightCount * 2 > limit2 - limit1 + 1)
ans = new Pair(right.element, rightCount);
return ans;
}
}
Last updated