Python prefix sum and bisect
Thoughts: \n\n- For an even index i, encoding[i] is the number of appreances of the encoding[i+1] in the list \n- Create two array, one for number of appearance
#### Thoughts: \n\n- For an even index i, `encoding[i]` is the number of appreances of the `encoding[i+1]` in the list \n- Create two array, one for number of appearance `self.counts` the other for the corresponding value `self.vals` . \n- Transform `self.counts` to prefix sum\n- Now you can binary search the insertion index while maintaining the sorted order of the `self.counts`. You can do this easily in Python with `bisect` library. \n\n#### Example \n\n[3, 8, 0, 9, 2, 5] is an encoding of [8, 8, 8, 5, 5] \nself.counts = [3, 2]\nself.vals = [8, 5] \nwhat you want to do now is to return 8 for query at index 0, 1, 2 and 5 for query at index 3, 4, and -1 for anything beyond  \n\n#### Solution \n\n```Python \nclass RLEIterator:\n\n    def __init__(self, encoding: List[int]):\n        self.counts = [-1] # -1 to avoid indexing error \n        self.vals = []\n        for i in range(len(encoding) // 2): \n            count, val = encoding[i*2], encoding[i*2+1] \n            if count > 0: \n                self.counts.append(count)\n                if len(self.counts) > 1: \n                    self.counts[-1] += self.counts[-2] # build the prefix sum \n                self.vals.append(val)\n        self.idx = -1 # an internal counter for handelling next calls \n\n\t# I created my own bisect module here but in python it\'s built-in \n    def bi(self, idx): \n        if idx > self.counts[-1]: \n            return -1 \n        l, r = 0, len(self.counts) - 1\n        while l <= r: \n            mid = l + (r - l) // 2\n            if self.counts[mid] < idx <= self.counts[mid+1]:\n                return mid \n            if idx > self.counts[mid+1]: \n                l = mid + 1\n            else: \n                r = mid - 1\n        \n    def next(self, n: int) -> int:\n        self.idx += n \n        # i = self.bi(self.idx)\n        i = bisect.bisect_left(self.counts, self.idx) - 1\n        return self.vals[i] if i < len(self.vals) else -1\n```
['Prefix Sum', 'Python']