Python3 FT 100%: Query Planning! TC O(sqrt(N*log(N))) Per Query, SC O(N)
Intuition\n\nWelcome to Big Chungus\'s ~4th ever FT 100% solution. Strap yourself in.\n\nThis is by far the most "fun" time complexity of any solution I\'ve sub
# Intuition\n\nWelcome to Big Chungus\'s ~4th ever FT 100% solution. Strap yourself in.\n\nThis is by far the most "fun" time complexity of any solution I\'ve submitted. $O\\left(\\sqrt{N \\log(N)}\\right)$ per query is a weird one. I\'ll prove it later.\n\n## Option 1: The Obvious\n\nWe can find the frequency of all elements in `[left, right]`, then compare to `threshold`.\n\n`threshold` is more than half the number of elements in the range, so we only need to look at the most common element. See `Counter.most_common(1)`.\n\n## Option 2: Huge Range\n\nIf the range is huge, then the obvious approach is O(N). But we have 1e4 queries.\n\nAt first we look like we\'re out of luck.\n\nBut we also know that if the interval size is O(N), then threshold is more than half, and thus also O(N).\n\n**There are at most O(1) elements with frequency O(N)**. If there were more, e.g. O(log(N)), we\'d have O(N log(N)) elements total - an obvious contradiction to having N elements.\n\nSo if the range is huge, we can do this\n* iterate over the most frequent element down to the least frequent\n* if the next frequency is less than threshold, break and return -1 immediately\n* count up how many copies of this value we have in `[left,right]`\n  * we can do this by storing the indices of each value\n  * then we can use binary search to find the position of the first index >= left and first index > right\n  * the difference in these positions is the number of copies in `[left,right]`\n\n# Approach\n\nWhen the range is small, we use Option 1.\n\nWhen the range is huge, we use Option 2.\n\nWhat about the middle? We have to pick one. Now introducing: **query planning**\n\n## Query Planning\n\nQuick background: SQL engines do this same approach. When you provide a query, there are usually several ways a SQL engine can process the results. It can do multiple scans over a table, or do just one scan over a table and store some intermediate results. It can create a hashmap or a tree map. And so on. Cost estimates for each of these can be computed based on parameters. The SQL engines *query planner* evaluates the costs of these options and chooses the cheapest one.\n\n**Side note:** if you use SQL a lot, *pay attention to the SQL server\'s query planning parameters.* Example: if you have a ton of memory, or even host your table from a ramdisk, Postgres recommends making a variety of changes to the query planning parameters. Especially the planner\'s cost parameters for random access overhead. Similarly, be careful around HDDs vs SSDs and their random access.\n\n### Cost Estimate of Option 1\n\nWe need to do an O(range) scan, followed by finding the most frequent element among O(range) unique values. This costs about 2*range in the worst case.\n\n### Cost Estimate of Option 2\n\nThere are at most about `N // threshold` values in `arr` with at least `threshold` copies.\n\nFor each of these `O(N//threshold)` values, we need to do two binary searches to get the number of ranges.\n\nI add a `self.const` parameter to account for the prefactor of binary search versus direct iteration - complexity analysis only gives us the asymptotic cost.\n\n### Minimal Cost Path and Complexity Analysis\n\nFor a range of length `L`, option one costs about 2L.\n\nOption 2 costs about const * N//L * log(N) for the N//L binary searches.\n\n**So we pick the smaller of `2L` and `const*N//L*log(N)`**\n\nSolving for `L` we get the `L <= sqrt(const/2 * N * log(N))`.\n* if L is less than this, we\'ll do option 1: direct iteration\n* if L is larger than this, we\'ll do option 2: trying the most frequent numbers\n\n**For option 1: cost is `O(L) <= O(sqrt(N*log(N)))`**\n\nFor option 2, that will mean the cost is\n```P\ncost = const*N*log(N) / sqrt(1/2)*sqrt(const*N*log(N))\n     = sqrt(2*const*N*log(N))\n     = O(sqrt(N*log(N)))\n```\n\n# Complexity\n- Time complexity: $O\\left( \\sqrt{N \\log(N)} \\right)$, see the query planning stuff above\n\n- Space complexity: $O(N)$ because we store the array, indices of all elements, and the frequencies of all elements.\n\n# Code\n```\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        # idea:\n        # for query left,right,threshold: we obviously need at least threshold copies total\n        # so for large thresholds there will only be a few elements\n        # for small thresholds, the range is small so we can fall back to direct iteration\n\n        # threshold is O(N): there are only O(1) numbers to consider: cumulative counts\n        # threshold is O(sqrt(N)): there are O(sqrt(N)) numbers to consider, and O(sqrt(N)) numbers in the range: uncanny valley\n        # threshold is O(1): there are O(N) numbers to consider, but only O(1) numbers in the range: direct iteration\n        \n        # For uncanny valley: O(Q sqrt(N)) is 1e4 * 1e2 roughly is 1e6, doable\n\n        # for cumulative counts, we want quick access to count of c in [l,r]\n        #    binary search? So it\'s really sqrt(N)*log(N)\n\n        # I considered a variety of other approaches, but\n        # divide-and-conquer is rough because most common element of two subranges can combine in many ways,\n        # i.e. top 2 of two intervals combined can be neither of the top two in individual intervals\n\n        counts = Counter(arr)\n        counts = list((f, v) for v, f in counts.items())\n        counts.sort(reverse=True) # by freq desc.\n\n        locs = defaultdict(list)\n        for i,a in enumerate(arr):\n            locs[a].append(i)\n\n        self.arr = arr\n        self.locs = locs # locs[x] is all indices of x, for log(N) frequency in interval\n        self.counts = counts # (f,v) pairs ordered by f desc.\n        self.const = 1.0 # lower const: prefer direct iteration over most-to-least-frequent trials\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        L = right-left+1\n\n        # Query cost: O(L) for direct iteration\n        #             len(arr)//threshold for numbers with at least `threshold` values\n        #                * log(L) to get cumulative counts in left,right for each\n        if 2*L < self.const*(len(self.arr)//threshold)*log(len(self.arr)):\n            # brute force: direct iteration, get counts then get max count and compare to threshold\n            counts = Counter(self.arr[i] for i in range(left, right+1))\n            v, f = counts.most_common(1)[0]\n            return v if f >= threshold else -1\n        else:\n            # check the few numbers with at least `threshold` copies\n            # use indices-of-left/right-index to get count of copies in [left, right]\n            for f,v in self.counts:\n                if f < threshold: break\n\n                idxs = self.locs[v]\n                kl = bisect_left(idxs, left)\n                if kl == len(idxs): continue\n                # idxs[kl] is left or higher\n                kr = bisect_right(idxs, right)\n                # idxs[kr] is 1 past end, or first value above right\n                \n                if kr-kl >= threshold: return v\n\n            # we tried all numbers with at least threshold counts\n            return -1\n            \n\n\n\n# Your MajorityChecker object will be instantiated and called as such:\n# obj = MajorityChecker(arr)\n# param_1 = obj.query(left,right,threshold)\n```
['Python3']