Algorithm

Problem Name: 1157. Online Majority Element In Subarray

Problem Link: https://leetcode.com/problems/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.

 

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

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const MajorityChecker = function(arr) {
  const map = new Map()
  for (let i = 0; i  <  arr.length; i++) {
    if (!map.has(arr[i])) map.set(arr[i], [i])
    else map.get(arr[i]).push(i)
  }
  this.pos = map
  this.arr = arr
}

function lbs(arr, val) {
  let lo = 0
  let hi = arr.length - 1
  if (arr[0] >= val) return 0
  else if (arr[hi] < val) return Infinity
  let mid
  while (hi - lo > 1) {
    mid = (hi + lo) >> 1
    if (arr[mid] === val) return mid
    else if (arr[mid]  <  val) lo = mid
    else if (arr[mid] > val) hi = mid
  }
  return hi
}

function rbs(arr, val) {
  let lo = 0
  let hi = arr.length - 1
  if (arr[hi] <= val) return hi
  else if (arr[lo] > val) return -Infinity
  let mid
  while (hi - lo > 1) {
    mid = (hi + lo) >> 1
    if (arr[mid] === val) return mid
    else if (arr[mid] < val) lo = mid
    else if (arr[mid] > val) hi = mid
  }
  return lo
}

MajorityChecker.prototype.query = function(left, right, threshold) {
  const { arr, pos } = this
  let c = 20
  while (c--) {
    const idx = left + Math.floor(Math.random() * (right - left + 1))
    const sort = pos.get(arr[idx])
    const lidx = lbs(sort, left)
    const ridx = rbs(sort, right)
    if (ridx - lidx + 1 >= threshold) return arr[idx]
  }
  return -1
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MajorityChecker", "query", "query", "query"] [[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]

Output

x
–
+
cmd
[null, 1, -1, 2]

#2 Code Example with Python Programming

Code - Python Programming


class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.dp = collections.defaultdict(list)
        for i, v in enumerate(arr):
            self.dp[v].append(i)
        self.occur = sorted([(len(v), k) for k, v in self.dp.items()], reverse = True)
        
    def query(self, left: int, right: int, threshold: int) -> int:
        for o, v in self.occur:
            if o < threshold: break
            l = self.dp[v]
            low = bisect.bisect_left(l, left)
            high = bisect.bisect_right(l, right)
            if high - low >= threshold:
                return v
        return -1
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MajorityChecker", "query", "query", "query"] [[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]

Output

x
–
+
cmd
[null, 1, -1, 2]
Advertisements

Demonstration

Previous
#1156 Leetcode Swap For Longest Repeated Character Substring Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1160 Leetcode Find Words That Can Be Formed by Characters Solution in C, C++, Java, JavaScript, Python, C# Leetcode