aboutsummaryrefslogtreecommitdiff
path: root/rle_iterator.py
blob: c7692e7f3bb83a93a8906dc4898a388676d57a2a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 900. RLE Iterator

"""
we can use run length encoding to encode a sequence of integers. in a run
length encoded array of even length encoding, for all even 'i', 'encoding[i]'
tells us the number of times that the non negative integer value 'encoding[i
+ 1]' is repeated in the sequence. given that a run length encoded array,
design an iterator that iterates through it.
"""


class RLEIterator(object):

    def __init__(self, encoding):
        """
        :type encoding: List[int]
        """
        self.vals = encoding
        self.i = 0

    def next(self, n):
        """
        :type n: int
        :rtype: int
        """
        while n > 0 and self.i < len(self.vals):
            if n > self.vals[self.i]:
                n -= self.vals[self.i]
                self.i += 2
            else:
                self.vals[self.i] -= n
                return self.vals[self.i + 1]
        return -1


if __name__ == "__main__":
    obj = RLEIterator([3, 8, 0, 9, 2, 5])
    print(obj.next(2))
    print(obj.next(1))
    print(obj.next(1))
    print(obj.next(2))