{"id":5410,"date":"2019-08-10T21:41:08","date_gmt":"2019-08-11T04:41:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5410"},"modified":"2019-08-10T22:24:55","modified_gmt":"2019-08-11T05:24:55","slug":"leetcode-1157-online-majority-element-in-subarray","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1157-online-majority-element-in-subarray\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1157. Online Majority Element In Subarray"},"content":{"rendered":"\n<p>Implementing the class&nbsp;<code>MajorityChecker<\/code>, which has the following API:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>MajorityChecker(int[] arr)<\/code>&nbsp;constructs an instance of MajorityChecker with the given array&nbsp;<code>arr<\/code>;<\/li><li><code>int query(int left, int right, int threshold)<\/code>&nbsp;has arguments&nbsp;such that:<ul><li><code>0 &lt;= left&nbsp;&lt;= right&nbsp;&lt; arr.length<\/code>&nbsp;representing a subarray of&nbsp;<code>arr<\/code>;<\/li><li><code>2 * threshold &gt; right - left + 1<\/code>, ie. the threshold is always a strict majority of the length of&nbsp;the subarray<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Each&nbsp;<code>query(...)<\/code>&nbsp;returns the element in&nbsp;<code>arr[left], arr[left+1], ..., arr[right]<\/code>that occurs at least&nbsp;<code>threshold<\/code>&nbsp;times, or&nbsp;<code>-1<\/code>&nbsp;if no such element exists.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);\nmajorityChecker.query(0,5,4); \/\/ returns 1\nmajorityChecker.query(0,3,3); \/\/ returns -1\nmajorityChecker.query(2,3,2); \/\/ returns 2\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= arr.length &lt;=&nbsp;20000<\/code><\/li><li><code>1 &lt;= arr[i]&nbsp;&lt;=&nbsp;20000<\/code><\/li><li>For each query,&nbsp;<code>0 &lt;= left &lt;= right &lt; len(arr)<\/code><\/li><li>For each query,&nbsp;<code>2 * threshold &gt; right - left + 1<\/code><\/li><li>The number of queries is at most&nbsp;<code>10000<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 0: Brute Force TLE<\/strong><\/h2>\n\n\n\n<p>For each range, find the majority element in O(n) time \/ O(n) or O(1) space.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Cache the range result<\/strong><\/h2>\n\n\n\n<p>Cache the result for each range: mode and frequency<\/p>\n\n\n\n<p>Time complexity: <br>init: O(1)<br>query: O(|right &#8211; left|)<br>total queries: O(sum(right_i &#8211; left_i)), right_i, left_i are bounds of unique ranges.<br>Space complexity: <br>init: O(1)<br>query: O(20000)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 568ms, 39.6 MB\nclass MajorityChecker {\npublic:\n  MajorityChecker(vector<int>& arr):nums(arr) {}\n\n  int query(int left, int right, int threshold) {        \n    int key = left * 20000 + right;\n    if (!seen.count(key)) {\n      int c[20001] = {0};\n      int best = (right - left) \/ 2;\n      int best_num = -1;\n      for (int i = left; i <= right; ++i) {\n        if (++c[nums[i]] > best) {\n          best = c[nums[i]];\n          best_num = nums[i];\n        }\n      }\n      seen[key] = {best_num, best};\n    }\n    return seen[key].second >= threshold ? seen[key].first : -1;\n  }\nprivate:\n  unordered_map<int, pair<int, int>> seen;\n  const vector<int>& nums;\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: HashTable + binary search<\/strong><\/h2>\n\n\n\n<p>Preprocessing: use a hashtable to store the indices of each element. And sort by frequency of the element in descending order.<br>Query: iterator over (total_freq, num) pair, if freq &gt;= threshold do a binary search to find the frequency of the given range for num in O(logn).<\/p>\n\n\n\n<p>Time complexity: <br>Init: O(nlogn)<br>Query: worst case: O(nlogn), best case: O(logn)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 156 ms, 44.7MB\nclass MajorityChecker {\npublic:\n  MajorityChecker(vector<int>& arr):nums(arr) {\n    const int max_n = *max_element(begin(nums), end(nums));\n    m = vector<vector<int>>(max_n + 1);\n    for (int i = 0; i < nums.size(); ++i) m[nums[i]].push_back(i);    \n    for (int n = 1; n <= max_n; ++n) {\n      if (m[n].size()) f.emplace_back(m[n].size(), n);\n    }\n    sort(rbegin(f), rend(f));    \n  }\n\n  int query(int left, int right, int threshold) {\n    for (const auto&#038; p : f) {\n      if (p.first < threshold) return -1;\n      int n = p.second;\n      const auto&#038; idx = m[n];\n      int count = upper_bound(begin(idx), end(idx), right) - lower_bound(begin(idx), end(idx), left);\n      if (count >= threshold) return n;\n    }\n    return -1;\n  }\nprivate:\n  const vector<int>& nums;\n  vector<vector<int>> m; \/\/ num -> {indices}\n  vector<pair<int, int>> f; \/\/ {freq, num}\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2+: Randomization<\/strong><\/h2>\n\n\n\n<p>Randomly pick a num in range [left, right] and check its freq, try k (e.g. 30) times. If a majority element exists, you should find it with error rate 1\/2^k.<\/p>\n\n\n\n<p>Time complexity:<br>Init: O(n)<br>Query: O(30 * logn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 240ms, 45.6MB\nclass MajorityChecker {\npublic:\n  MajorityChecker(vector<int>& arr):nums(arr) {  \n    for (int i = 0; i < nums.size(); ++i) m[nums[i]].push_back(i);    \n  }\n\n  int query(int left, int right, int threshold) {    \n    for (int i = 0; i < 30; ++i) {\n      int n = nums[rand() % (right - left + 1) + left];\n      const auto&#038; idx = m[n];\n      int count = upper_bound(begin(idx), end(idx), right) - lower_bound(begin(idx), end(idx), left);\n      if (count >= threshold) return n;\n    }\n    return -1;\n  }\nprivate:\n  unordered_map<int, vector<int>> m; \/\/ num -> {indices}  \n  const vector<int>& nums;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Implementing the class&nbsp;MajorityChecker, which has the following API: MajorityChecker(int[] arr)&nbsp;constructs an instance of MajorityChecker with the given array&nbsp;arr; int query(int left, int right, int threshold)&nbsp;has&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[217,98],"class_list":["post-5410","post","type-post","status-publish","format-standard","hentry","category-array","tag-hard","tag-range-query","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5410","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5410"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5410\/revisions"}],"predecessor-version":[{"id":5417,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5410\/revisions\/5417"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5410"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5410"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5410"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}