Some basic knowledge to understand the following methods and codes:\n\n1. For a given interval `[l, r]` and `threshold`, we would like to find the majority which occurs at least `threshold` times. The problem also gives an inequality `2 * threshold > right - left + 1`, which means the majority must occur more than half. We denote the majority which satisfies the inequality as "more than half" majority.\n\n2. For the "more than half" majority, the following theorem always holds: if we split the interval `[l, r]` into consecutive sub-intervals `[l, a_1], [a_1+1, a_2], ..., [a_{n-1}+1, a_n], [a_n+1, r]`, the "more than half" majority of interval `[l, r]` (if it exists) should be also the "more than half" majority of at least one sub-interval. This can be proved by contradiction.\n\n3. By the theorem in 2, we can split the interval `[l, r]` into sub-intervals and find the "more than half" majority of each sub-interval and check whether it is the "more than half" majority of the interval `[l, r]`.\n\n4. We can use [Boyer\u2013Moore majority vote algorithm](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm) to find the "more than half" majority in `O(n)` time.\n\n5. We can use a `unordered_map>` to store the positions of each number in `[l, r]`. The key in the `unordered_map` represents a number and the value represents the positions of that number in increasing order. Thus we can count the occurrences of a number in a given interval `[l, r]` in `O(log(n))` time by using binary search (in C++ we can use `lower_bound` and `upper_bound` to simplify the code).\n\n6. We can combine 4 and 5 together to check whether the "more than half" majority occurs at least `threshold` times. The time complexity is the same as 4, since `O(n + log(n)) = O(n)` holds.\n\nI will show 4 different method with brief explanations below. I will use the sign `No.x` to reference the basic knowledge with number `x`. `No.6` is often used to find the "more than half" majority in a short sub-interval, while `No.5` is often used to find the "more than half" majority in a long interval after finishing the sub-interval calculations, as `No.3` states.\n\nRandom Pick:\nAs the majority occurs more than half in the interval `[l, r]`, we will have the probability of more than `1/2` to find the "more than half" majority if we randomly pick a number in the interval. Thus, if we randomly pick `try_bound` times, we will have the probability of `(1-(1/2)) ** try_bound` not to find the "more than half" majority. The probability will be less than `1e-6` if we set `try_bound` as `20`. If we find nothing in `try_bound` times, we can claim that there is no "more than half" majority.\nHere we use `No.5` to count the occurrences of a randomly picked number.\n\nRuntime: ~200 ms\nPre-calculation: `O(n)`\nQuery: `O(try_bound * log(n))`\n\n```\nclass MajorityChecker {\nprivate:\n unordered_map> pos;\n vector a;\n int try_bound;\n \npublic:\n MajorityChecker(vector& arr): a(arr) {\n srand(time(nullptr));\n for (int i = 0; i < arr.size(); ++i) {\n pos[arr[i]].push_back(i);\n }\n try_bound = 20;\n }\n \n int get_occurrence(int num, int l, int r) {\n auto iter = pos.find(num);\n if (iter == pos.end()) {\n return 0;\n }\n const auto& vec = iter->second;\n auto iter_l = lower_bound(vec.begin(), vec.end(), l);\n if (iter_l == vec.end()) {\n return 0;\n }\n auto iter_r = upper_bound(vec.begin(), vec.end(), r);\n return iter_r - iter_l;\n }\n \n int get_random(int l, int r) {\n return rand() % (r - l + 1) + l;\n }\n \n int query(int left, int right, int threshold) {\n for (int i = 0; i < try_bound; ++i) {\n int elem = a[get_random(left, right)];\n if (get_occurrence(elem, left, right) >= threshold) {\n return elem;\n }\n }\n return -1;\n }\n};\n```\n\nTrade-off:\nThis method is based on the fact that number of "popular" numbers (i.e. a number which occurs at least `t` times) cannot exceed `n/t`. Thus, if the `threshold` in a given query is not less than `t`, there is only `n/t` candidate "more than half" majorities.\nWe can design an algorithm to handle different queries with different methods. For the queries with `threshold` less than `t`, the length of interval `[l, r]` will also smaller than `2t`, so we can simply use `No.6` to find the "more than half" majority in `O(t)` time. For the queries with `threshold` more than `t`, we iterate through the "popular" numbers and use `No.5` to check whether it is a "more than half" majority in `[l, r]`. This is solved in `O((n/t) * log(n/t))` time, `O(n/t)` for the iteration and `O(log(n/t))` for `No.5`. Thus, the total time complexity is the maximum of `O(t)` and `O((n/t) * log(n/t))`. We can do a trade-off by solving the equation `t = (n/t) * log(n/t)`, but it is too difficult. However, we can simply set `t` as `sqrt(n)` to get a pretty good trade-off, and the time complexity will be `O(sqrt(n) * log(n))`.\n\nRuntime: ~200 ms\nPre-calculation: `O(n)`\nQuery: `O(sqrt(n) * log(n))`\n\n```\nclass MajorityChecker {\nprivate:\n unordered_map> pos;\n unordered_set popular;\n vector a;\n int lookup_bound;\n \npublic:\n MajorityChecker(vector& arr): a(arr) {\n for (int i = 0; i < arr.size(); ++i) {\n pos[arr[i]].push_back(i);\n }\n lookup_bound = round(sqrt(arr.size()));\n for (const auto& [key, value]: pos) {\n if (value.size() >= lookup_bound) {\n popular.insert(key);\n }\n }\n }\n \n int vote(int l, int r) {\n int target = a[l], occ = 1;\n for (int i = l + 1; i <= r; ++i) {\n if (a[i] == target) {\n ++occ;\n }\n else {\n --occ;\n if (occ < 0) {\n target = a[i];\n occ = 1;\n }\n }\n }\n int cnt = 0;\n for (int i = l; i <= r; ++i) {\n if (a[i] == target) {\n ++cnt;\n }\n }\n if (cnt * 2 > r - l + 1) {\n return target;\n }\n return -1;\n }\n \n int get_occurrence(int num, int l, int r) {\n auto iter = pos.find(num);\n if (iter == pos.end()) {\n return 0;\n }\n const auto& vec = iter->second;\n auto iter_l = lower_bound(vec.begin(), vec.end(), l);\n if (iter_l == vec.end()) {\n return 0;\n }\n auto iter_r = upper_bound(vec.begin(), vec.end(), r);\n return iter_r - iter_l;\n }\n \n int query(int left, int right, int threshold) {\n if (threshold <= lookup_bound) {\n int candidate = vote(left, right);\n if (candidate != -1 && get_occurrence(candidate, left, right) >= threshold) {\n return candidate;\n }\n return -1;\n }\n else {\n for (const int& elem: popular) {\n if (get_occurrence(elem, left, right) >= threshold) {\n return elem;\n }\n }\n return -1;\n }\n }\n};\n```\n\nSegment tree:\nSegment tree is a perfect data structure for this problem because it can divide an interval into consecutive sub-intervals. The nodes in the segment tree store the "more than half" majority (if it exists) or `-1` of the corresponding interval `[l, r]`. We use `No.5` to merge the interval `[l, mid]` and `[mid + 1, r]` in the "build tree" process.\nDuring the query process, we can search the interval `[l, r]` on the segment tree and get `O(log(n))` sub-intervals. For each sub-interval, we use `No.5` to check if it is the "more than half" majority of `[l, r]`, which is another `O(log(n))` time.\n\nRuntime: ~200ms\nPre-calculation: `O(n * log(n))`\nQuery: `O(log(n) * log(n))`\n\n```\nclass MajorityChecker {\nprivate:\n unordered_map> pos;\n vector tree;\n vector a;\n \npublic:\n MajorityChecker(vector& arr): a(arr) {\n for (int i = 0; i < arr.size(); ++i) {\n pos[arr[i]].push_back(i);\n }\n tree = vector(arr.size() * 4, -1);\n build_tree(1, 0, arr.size() - 1);\n }\n \n void build_tree(int tree_pos, int l, int r) {\n if (l == r) {\n tree[tree_pos] = a[l];\n return;\n }\n int mid = (l + r) >> 1;\n build_tree(tree_pos * 2, l, mid);\n build_tree(tree_pos * 2 + 1, mid + 1, r);\n if (tree[tree_pos * 2] != -1 && get_occurrence(tree[tree_pos * 2], l, r) * 2 > r - l + 1) {\n tree[tree_pos] = tree[tree_pos * 2];\n }\n else if (tree[tree_pos * 2 + 1] != -1 && get_occurrence(tree[tree_pos * 2 + 1], l, r) * 2 > r - l + 1) {\n tree[tree_pos] = tree[tree_pos * 2 + 1];\n }\n }\n \n pair query(int tree_pos, int l, int r, int queryl, int queryr) {\n if (l > queryr || r < queryl) {\n return make_pair(-1, -1);\n }\n if (queryl <= l && r <= queryr) {\n if (tree[tree_pos] == -1) {\n return make_pair(-1, -1);\n }\n int occ = get_occurrence(tree[tree_pos], queryl, queryr);\n if (occ * 2 > queryr - queryl + 1) {\n return make_pair(tree[tree_pos], occ);\n }\n else {\n return make_pair(-1, -1);\n }\n }\n int mid = (l + r) >> 1;\n pair res_l = query(tree_pos * 2, l, mid, queryl, queryr);\n if (res_l.first > -1) {\n return res_l;\n }\n pair res_r = query(tree_pos * 2 + 1, mid + 1, r, queryl, queryr);\n if (res_r.first > -1) {\n return res_r;\n }\n return make_pair(-1, -1);\n }\n \n int get_occurrence(int num, int l, int r) {\n auto iter = pos.find(num);\n if (iter == pos.end()) {\n return 0;\n }\n const auto& vec = iter->second;\n auto iter_l = lower_bound(vec.begin(), vec.end(), l);\n if (iter_l == vec.end()) {\n return 0;\n }\n auto iter_r = upper_bound(vec.begin(), vec.end(), r);\n return iter_r - iter_l;\n }\n \n int query(int left, int right, int threshold) {\n pair ans = query(1, 0, a.size() - 1, left, right);\n if (ans.second >= threshold) {\n return ans.first;\n }\n return -1;\n }\n};\n```\n\nBucket:\nThe bucket method also focus on splitting `[l, r]` into sub-intervals. We break the interval into `t` buckets with size `n/t`. We pre-calculate the "more than half" majority of each bucket by `No.6`. For a given query `[l, r]`, we find the bucket id `b_l` and `b_r` which contains `l` and `r`. If `b_l` equals to `b_r`, it means the whole interval lies in one bucket, we can use `No.6` to find the "more than half" majority in `O(t)` time. If `b_l` is not equal to `b_r`, we can divide the interval into `[l, r_border(b_l)], b_{l+1}, ..., b_{r-1}, [l_border(b_r), r]`, where `l_border` and `r_border` represent the left and right border of a bucket. We find the "more than half" majority of complete buckets by the pre-calculation and the first & last sub-interval by `No.6`. We get no more than `n/t` candidates now and we check each by `No.5` to find the "more than half" majority. The time complexity is `O(t + (n/t) * log(t))`, which is more than the previous `O(t)`. Thus we come to the trade-off to minimize `O(t + (n/t) * log(t))`. We can set `t` as `sqrt(n)` to get a pretty good trade-off `O(sqrt(n) * log(n))`.\n\nRuntime: ~400ms\nPre-calculation: `O(n)`\nQuery: `O(sqrt(n) * log(n))`\n\n```\nclass MajorityChecker {\nprivate:\n unordered_map> pos;\n vector a;\n vector bucket;\n int bucket_size;\n \n \npublic:\n MajorityChecker(vector& arr): a(arr) {\n for (int i = 0; i < arr.size(); ++i) {\n pos[arr[i]].push_back(i);\n }\n bucket_size = round(sqrt(a.size()));\n int l = 0;\n while (l < a.size()) {\n int r = min(l + bucket_size, (int)a.size()) - 1;\n bucket.push_back(vote(l, r));\n l += bucket_size;\n }\n }\n \n int vote(int l, int r) {\n int target = a[l], occ = 1;\n for (int i = l + 1; i <= r; ++i) {\n if (a[i] == target) {\n ++occ;\n }\n else {\n --occ;\n if (occ < 0) {\n target = a[i];\n occ = 1;\n }\n }\n }\n int cnt = 0;\n for (int i = l; i <= r; ++i) {\n if (a[i] == target) {\n ++cnt;\n }\n }\n if (cnt * 2 > r - l + 1) {\n return target;\n }\n return -1;\n }\n \n int get_occurrence(int num, int l, int r) {\n auto iter = pos.find(num);\n if (iter == pos.end()) {\n return 0;\n }\n const auto& vec = iter->second;\n auto iter_l = lower_bound(vec.begin(), vec.end(), l);\n if (iter_l == vec.end()) {\n return 0;\n }\n auto iter_r = upper_bound(vec.begin(), vec.end(), r);\n return iter_r - iter_l;\n }\n \n int query(int left, int right, int threshold) {\n int bucket_l = left / bucket_size;\n int bucket_r = right / bucket_size;\n if (bucket_l == bucket_r) {\n int candidate = vote(left, right);\n if (candidate != -1 && get_occurrence(candidate, left, right) >= threshold) {\n return candidate;\n }\n return -1;\n }\n else {\n int vote_l = vote(left, (bucket_l + 1) * bucket_size - 1);\n int vote_r = vote(bucket_r * bucket_size, right);\n if (vote_l != -1 && get_occurrence(vote_l, left, right) >= threshold) {\n return vote_l;\n }\n if (vote_r != -1 && get_occurrence(vote_r, left, right) >= threshold) {\n return vote_r;\n }\n for (int i = bucket_l + 1; i < bucket_r; ++i) {\n int occ = get_occurrence(bucket[i], left, right);\n if (occ >= threshold) {\n return bucket[i];\n }\n }\n return -1;\n }\n }\n};\n```\n

Online Majority Element In Subarray

Problem Description

Problem Description

Answer Panel