1157. Online Majority Element In Subarray LeetCode Solution
In this guide, you will get 1157. Online Majority Element In Subarray LeetCode Solution with the best time and space complexity. The solution to Online Majority Element In Subarray problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Online Majority Element In Subarray
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.
1157. Online Majority Element In Subarray LeetCode Solution in C++
class MajorityChecker {
public:
MajorityChecker(vector<int>& arr) : arr(arr) {
for (int i = 0; i < arr.size(); ++i)
numToIndices[arr[i]].push_back(i);
}
int query(int left, int right, int threshold) {
for (int i = 0; i < kTimes; ++i) {
const int randIndex = rand() % (right - left + 1) + left;
const int num = arr[randIndex];
const vector<int>& indices = numToIndices[num];
const auto lit = ranges::lower_bound(indices, left);
const auto rit = ranges::upper_bound(indices, right);
if (rit - lit >= threshold)
return num;
}
return -1;
}
private:
const vector<int> arr;
static constexpr int kTimes = 20; // 2^kTimes >> |arr| = n
unordered_map<int, vector<int>> numToIndices;
}; /* code provided by PROGIEZ */
1157. Online Majority Element In Subarray LeetCode Solution in Java
class MajorityChecker {
public MajorityChecker(int[] arr) {
this.arr = arr;
for (int i = 0; i < arr.length; ++i) {
if (!numToIndices.containsKey(arr[i]))
numToIndices.put(arr[i], new ArrayList<>());
numToIndices.get(arr[i]).add(i);
}
}
public int query(int left, int right, int threshold) {
for (int i = 0; i < kTimes; ++i) {
final int randIndex = rand.nextInt(right - left + 1) + left;
final int num = arr[randIndex];
List<Integer> indices = numToIndices.get(num);
final int l = firstGreaterEqual(indices, left);
final int r = firstGreaterEqual(indices, right + 1);
if (r - l >= threshold)
return num;
}
return -1;
}
private static final int kTimes = 20; // 2^kTimes >> |arr|
private int[] arr;
private Map<Integer, List<Integer>> numToIndices = new HashMap<>();
private Random rand = new Random();
private int firstGreaterEqual(List<Integer> A, int target) {
final int i = Collections.binarySearch(A, target);
return i < 0 ? -i - 1 : i;
}
} // code provided by PROGIEZ
1157. Online Majority Element In Subarray LeetCode Solution in Python
class MajorityChecker:
def __init__(self, arr: list[int]):
self.arr = arr
self.kTimes = 20 # 2^kTimes >> |arr|
self.numToIndices = collections.defaultdict(list)
for i, a in enumerate(self.arr):
self.numToIndices[a].append(i)
def query(self, left: int, right: int, threshold: int) -> int:
for _ in range(self.kTimes):
randIndex = random.randint(left, right)
num = self.arr[randIndex]
indices = self.numToIndices[num]
l = bisect.bisect_left(indices, left)
r = bisect.bisect_right(indices, right)
if r - l >= threshold:
return num
return -1 # code by PROGIEZ
