Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1157.html
1157. Online Majority Element In Subarray
Level
Hard
Description
Implementing the class MajorityChecker
, which has the following API:
MajorityChecker(int[] arr)
constructs an instance of MajorityChecker with the given array arr;int query(int left, int right, int threshold)
has arguments such that:0 <= left <= right < arr.length
representing a subarray of arr;2 * threshold > right - left + 1
, ie. the threshold is always a strict majority of the length of the subarray
Each query(...)
returns the element in arr[left], arr[left+1], ..., arr[right]
that occurs at least threshold
times, or -1
if no such element exists.
Example:
MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2
Constraints:
1 <= arr.length <= 20000
1 <= arr[i] <= 20000
- For each query,
0 <= left <= right < len(arr)
- For each query,
2 * threshold > right - left + 1
- The number of queries is at most
10000
Solution
Maintain an array in the class. For the constructor, simply assign the array to the array in the class. For method query
, since the elements are in the range [1, 20000]
, create an array count
of length 20001, and loop over the array from index left
to index right
. If at one point, a number’s count reaches threshold
, then return the number. If no such number is met, return -1.
-
class MajorityChecker { int[] arr; public MajorityChecker(int[] arr) { this.arr = arr; } public int query(int left, int right, int threshold) { int[] count = new int[20001]; for (int i = left; i <= right; i++) { int num = arr[i]; if (++count[num] == threshold) return num; } return -1; } } /** * Your MajorityChecker object will be instantiated and called as such: * MajorityChecker obj = new MajorityChecker(arr); * int param_1 = obj.query(left,right,threshold); */ ############ class Node { int l, r; int x, cnt; } class SegmentTree { private Node[] tr; private int[] nums; public SegmentTree(int[] nums) { int n = nums.length; this.nums = nums; tr = new Node[n << 2]; for (int i = 0; i < tr.length; ++i) { tr[i] = new Node(); } build(1, 1, n); } private void build(int u, int l, int r) { tr[u].l = l; tr[u].r = r; if (l == r) { tr[u].x = nums[l - 1]; tr[u].cnt = 1; return; } int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } public int[] query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) { return new int[] {tr[u].x, tr[u].cnt}; } int mid = (tr[u].l + tr[u].r) >> 1; if (r <= mid) { return query(u << 1, l, r); } if (l > mid) { return query(u << 1 | 1, l, r); } var left = query(u << 1, l, r); var right = query(u << 1 | 1, l, r); if (left[0] == right[0]) { left[1] += right[1]; } else if (left[1] >= right[1]) { left[1] -= right[1]; } else { right[1] -= left[1]; left = right; } return left; } private void pushup(int u) { if (tr[u << 1].x == tr[u << 1 | 1].x) { tr[u].x = tr[u << 1].x; tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt; } else if (tr[u << 1].cnt >= tr[u << 1 | 1].cnt) { tr[u].x = tr[u << 1].x; tr[u].cnt = tr[u << 1].cnt - tr[u << 1 | 1].cnt; } else { tr[u].x = tr[u << 1 | 1].x; tr[u].cnt = tr[u << 1 | 1].cnt - tr[u << 1].cnt; } } } class MajorityChecker { private SegmentTree tree; private Map<Integer, List<Integer>> d = new HashMap<>(); public MajorityChecker(int[] arr) { tree = new SegmentTree(arr); for (int i = 0; i < arr.length; ++i) { d.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i); } } public int query(int left, int right, int threshold) { int x = tree.query(1, left + 1, right + 1)[0]; int l = search(d.get(x), left); int r = search(d.get(x), right + 1); return r - l >= threshold ? x : -1; } private int search(List<Integer> arr, int x) { int left = 0, right = arr.size(); while (left < right) { int mid = (left + right) >> 1; if (arr.get(mid) >= x) { right = mid; } else { left = mid + 1; } } return left; } } /** * Your MajorityChecker object will be instantiated and called as such: * MajorityChecker obj = new MajorityChecker(arr); * int param_1 = obj.query(left,right,threshold); */
-
class Node { public: int l = 0, r = 0; int x = 0, cnt = 0; }; using pii = pair<int, int>; class SegmentTree { public: SegmentTree(vector<int>& nums) { this->nums = nums; int n = nums.size(); tr.resize(n << 2); for (int i = 0; i < tr.size(); ++i) { tr[i] = new Node(); } build(1, 1, n); } pii query(int u, int l, int r) { if (tr[u]->l >= l && tr[u]->r <= r) { return {tr[u]->x, tr[u]->cnt}; } int mid = (tr[u]->l + tr[u]->r) >> 1; if (r <= mid) { return query(u << 1, l, r); } if (l > mid) { return query(u << 1 | 1, l, r); } auto left = query(u << 1, l, r); auto right = query(u << 1 | 1, l, r); if (left.first == right.first) { left.second += right.second; } else if (left.second >= right.second) { left.second -= right.second; } else { right.second -= left.second; left = right; } return left; } private: vector<Node*> tr; vector<int> nums; void build(int u, int l, int r) { tr[u]->l = l; tr[u]->r = r; if (l == r) { tr[u]->x = nums[l - 1]; tr[u]->cnt = 1; return; } int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } void pushup(int u) { if (tr[u << 1]->x == tr[u << 1 | 1]->x) { tr[u]->x = tr[u << 1]->x; tr[u]->cnt = tr[u << 1]->cnt + tr[u << 1 | 1]->cnt; } else if (tr[u << 1]->cnt >= tr[u << 1 | 1]->cnt) { tr[u]->x = tr[u << 1]->x; tr[u]->cnt = tr[u << 1]->cnt - tr[u << 1 | 1]->cnt; } else { tr[u]->x = tr[u << 1 | 1]->x; tr[u]->cnt = tr[u << 1 | 1]->cnt - tr[u << 1]->cnt; } } }; class MajorityChecker { public: MajorityChecker(vector<int>& arr) { tree = new SegmentTree(arr); for (int i = 0; i < arr.size(); ++i) { d[arr[i]].push_back(i); } } int query(int left, int right, int threshold) { int x = tree->query(1, left + 1, right + 1).first; auto l = lower_bound(d[x].begin(), d[x].end(), left); auto r = lower_bound(d[x].begin(), d[x].end(), right + 1); return r - l >= threshold ? x : -1; } private: unordered_map<int, vector<int>> d; SegmentTree* tree; }; /** * Your MajorityChecker object will be instantiated and called as such: * MajorityChecker* obj = new MajorityChecker(arr); * int param_1 = obj->query(left,right,threshold); */
-
class Node: def __init__(self): self.l = self.r = 0 self.x = self.cnt = 0 class SegmentTree: def __init__(self, nums): self.nums = nums n = len(nums) self.tr = [Node() for _ in range(n << 2)] self.build(1, 1, n) def build(self, u, l, r): self.tr[u].l, self.tr[u].r = l, r if l == r: self.tr[u].x = self.nums[l - 1] self.tr[u].cnt = 1 return mid = (l + r) >> 1 self.build(u << 1, l, mid) self.build(u << 1 | 1, mid + 1, r) self.pushup(u) def query(self, u, l, r): if self.tr[u].l >= l and self.tr[u].r <= r: return self.tr[u].x, self.tr[u].cnt mid = (self.tr[u].l + self.tr[u].r) >> 1 if r <= mid: return self.query(u << 1, l, r) if l > mid: return self.query(u << 1 | 1, l, r) x1, cnt1 = self.query(u << 1, l, r) x2, cnt2 = self.query(u << 1 | 1, l, r) if x1 == x2: return x1, cnt1 + cnt2 if cnt1 >= cnt2: return x1, cnt1 - cnt2 else: return x2, cnt2 - cnt1 def pushup(self, u): if self.tr[u << 1].x == self.tr[u << 1 | 1].x: self.tr[u].x = self.tr[u << 1].x self.tr[u].cnt = self.tr[u << 1].cnt + self.tr[u << 1 | 1].cnt elif self.tr[u << 1].cnt >= self.tr[u << 1 | 1].cnt: self.tr[u].x = self.tr[u << 1].x self.tr[u].cnt = self.tr[u << 1].cnt - self.tr[u << 1 | 1].cnt else: self.tr[u].x = self.tr[u << 1 | 1].x self.tr[u].cnt = self.tr[u << 1 | 1].cnt - self.tr[u << 1].cnt class MajorityChecker: def __init__(self, arr: List[int]): self.tree = SegmentTree(arr) self.d = defaultdict(list) for i, x in enumerate(arr): self.d[x].append(i) def query(self, left: int, right: int, threshold: int) -> int: x, _ = self.tree.query(1, left + 1, right + 1) l = bisect_left(self.d[x], left) r = bisect_left(self.d[x], right + 1) return x if r - l >= threshold else -1 # Your MajorityChecker object will be instantiated and called as such: # obj = MajorityChecker(arr) # param_1 = obj.query(left,right,threshold)
-
type node struct { l, r, x, cnt int } type segmentTree struct { nums []int tr []*node } type pair struct{ x, cnt int } func newSegmentTree(nums []int) *segmentTree { n := len(nums) tr := make([]*node, n<<2) for i := range tr { tr[i] = &node{} } t := &segmentTree{nums, tr} t.build(1, 1, n) return t } func (t *segmentTree) build(u, l, r int) { t.tr[u].l, t.tr[u].r = l, r if l == r { t.tr[u].x = t.nums[l-1] t.tr[u].cnt = 1 return } mid := (l + r) >> 1 t.build(u<<1, l, mid) t.build(u<<1|1, mid+1, r) t.pushup(u) } func (t *segmentTree) query(u, l, r int) pair { if t.tr[u].l >= l && t.tr[u].r <= r { return pair{t.tr[u].x, t.tr[u].cnt} } mid := (t.tr[u].l + t.tr[u].r) >> 1 if r <= mid { return t.query(u<<1, l, r) } if l > mid { return t.query(u<<1|1, l, r) } left, right := t.query(u<<1, l, r), t.query(u<<1|1, l, r) if left.x == right.x { left.cnt += right.cnt } else if left.cnt >= right.cnt { left.cnt -= right.cnt } else { right.cnt -= left.cnt left = right } return left } func (t *segmentTree) pushup(u int) { if t.tr[u<<1].x == t.tr[u<<1|1].x { t.tr[u].x = t.tr[u<<1].x t.tr[u].cnt = t.tr[u<<1].cnt + t.tr[u<<1|1].cnt } else if t.tr[u<<1].cnt >= t.tr[u<<1|1].cnt { t.tr[u].x = t.tr[u<<1].x t.tr[u].cnt = t.tr[u<<1].cnt - t.tr[u<<1|1].cnt } else { t.tr[u].x = t.tr[u<<1|1].x t.tr[u].cnt = t.tr[u<<1|1].cnt - t.tr[u<<1].cnt } } type MajorityChecker struct { tree *segmentTree d map[int][]int } func Constructor(arr []int) MajorityChecker { tree := newSegmentTree(arr) d := map[int][]int{} for i, x := range arr { d[x] = append(d[x], i) } return MajorityChecker{tree, d} } func (this *MajorityChecker) Query(left int, right int, threshold int) int { x := this.tree.query(1, left+1, right+1).x l := sort.SearchInts(this.d[x], left) r := sort.SearchInts(this.d[x], right+1) if r-l >= threshold { return x } return -1 } /** * Your MajorityChecker object will be instantiated and called as such: * obj := Constructor(arr); * param_1 := obj.Query(left,right,threshold); */