golang solution with Runtime 285 ms Beats 100.00%
Intuition\nThe MajorityChecker is designed to efficiently handle queries about a given range of elements in an array. Each query aims to find an element that ap
# Intuition\nThe MajorityChecker is designed to efficiently handle queries about a given range of elements in an array. Each query aims to find an element that appears at least a certain number of times within the specified range.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n**1. Constructor Function:**\n\nWhen creating an instance of MajorityChecker, the constructor initializes the internal data structures required for efficient querying.\nIt creates a map pos where each key represents a unique element from the input array, and the corresponding value is an array containing the indices where that element occurs in the input array.\nThe tryBound variable is set to 20 by default, representing the number of attempts allowed to find a majority element in a query.\n\n**2.getOccurrence Function:**\nThis function retrieves the number of occurrences of a specific element within a given range [l, r].\nIt utilizes binary search to find the positions of the element within the specified range.\n\n**3.getRandom Function:**\nThis function generates a random integer between l and r, inclusive.\n\n**4.Query Function:**\n\nFor each query, the Query function tries to find an element that appears at least threshold times within the given range [left, right].\nIt makes tryBound attempts to find such an element, each time selecting a random index within the range and checking its occurrence count using the getOccurrence function.\nIf an element satisfying the threshold condition is found, it is returned. Otherwise, -1 is returned.\n\n# Complexity\n**Constructor:** The constructor function has a time complexity of O(n), where n is the length of the input array. It iterates through the array to populate the pos map.\n\n**getOccurrence Function:** The time complexity of this function is O(log(m)), where m is the number of occurrences of the queried element within the given range [l, r]. The binary search operation ensures efficient lookup.\n![Screenshot 2024-03-12 at 4.18.27 PM.png](https://assets.leetcode.com/users/images/95cb84b8-00b5-450a-89b7-4aaa47db0888_1710240767.097817.png)\n\n**getRandom Function:** This function has a time complexity of O(1) as it performs basic arithmetic operations to generate a random integer.\nQuery Function: The time complexity of each query operation is O(k * log(m)), where k is the value of tryBound and m is the number of occurrences of the queried element within the given range [left, right]. Since the number of attempts is limited, the overall time complexity is bounded.\n\n# Code\n```\npackage main\n\nimport (\n\t"math/rand"\n\t"sort"\n\t"time"\n)\n\ntype MajorityChecker struct {\n\tpos      map[int][]int\n\ta        []int\n\ttryBound int\n}\n\nfunc (m *MajorityChecker) getOccurrence(num, l, r int) int {\n\tvec, ok := m.pos[num]\n\tif !ok {\n\t\treturn 0\n\t}\n\n\titerL := sort.Search(len(vec), func(i int) bool { return vec[i] >= l })\n\tif iterL == len(vec) || vec[iterL] > r {\n\t\treturn 0\n\t}\n\n\titerR := sort.Search(len(vec), func(i int) bool { return vec[i] > r })\n\n\treturn iterR - iterL\n}\n\nfunc (m *MajorityChecker) getRandom(l, r int) int {\n\treturn rand.Intn(r-l+1) + l\n}\n\nfunc Constructor(arr []int) MajorityChecker {\n\tm := MajorityChecker{\n\t\tpos:      make(map[int][]int),\n\t\ta:        arr,\n\t\ttryBound: 20,\n\t}\n\trand.Seed(time.Now().UnixNano())\n\n\tfor i := 0; i < len(arr); i++ {\n\t\tm.pos[arr[i]] = append(m.pos[arr[i]], i)\n\t}\n\n\treturn m\n}\n\nfunc (this *MajorityChecker) Query(left, right, threshold int) int {\n\tfor i := 0; i < this.tryBound; i++ {\n\t\telem := this.a[this.getRandom(left, right)]\n\t\tif this.getOccurrence(elem, left, right) >= threshold {\n\t\t\treturn elem\n\t\t}\n\t}\n\treturn -1\n}\n\n```
['Go']