1262. Online Majority Element In Subarray¶

Difficulty: Hard

LeetCode Problem View on GitHub

1262. Online Majority Element In Subarray

Hard

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:

MajorityChecker(int[] arr) Initializes the instance of the class with the given array arr.
int query(int left, int right, int threshold) returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element 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]

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 * 10⁴
1 <= arr[i] <= 2 * 10⁴
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
At most 10⁴ calls will be made to query.

Solution¶

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;
import java.util.TreeSet;

class MajorityChecker {
    private HashMap<Integer, ArrayList<Integer >> map;
    private int nums[];
    public MajorityChecker(int[] arr) {
        int n = arr.length;
        map = new HashMap<>();
        nums = new int[n];
        for (int i = 0; i < n; i++)
            nums[i] = arr[i];
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i]))
                map.put(arr[i], new ArrayList<>());
            map.get(arr[i]).add(i);
        }
    }

    public int query(int left, int right, int threshold) {
        for (int i = 0; i < 10; i++) {
            Random rand = new Random();
            int index = rand.nextInt(right - left + 1) + left;
            int val = nums[index];
            ArrayList<Integer> idx = new ArrayList<>();
            idx = map.get(val);
            if (bsRight(idx, right) - bsLeft(idx, left) + 1 >= threshold)
                return val;
        }
        return -1;
    }

    private int bsLeft(ArrayList<Integer> arr, int left) {
        int n = arr.size();
        int low = 0, high = n - 1, ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr.get(mid) >= left) {
                ans = mid;
                high = mid - 1;
            } else
                low = mid + 1;
        }
        return ans;
    }

    private int bsRight(ArrayList<Integer> arr, int right) {
        int n = arr.size();
        int low = 0, high = n - 1, ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr.get(mid) <= right) {
                ans = mid;
                low = mid + 1;
            } else
                high = mid - 1;
        }
        return ans;
    }
}

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

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here