LC-0900 Medium LeetCode

900. RLE Iterator

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 59% Topics: Array, Design, Counting, Iterator

Reading material

Arrays & Hashing 12 min Design (Data Structures) 14 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class RLEIterator(object):

    def __init__(self, A):
        """
        :type A: List[int]
        """
        self.__A = A
        self.__i = 0
        self.__cnt = 0

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

Solution from kamyu104/LeetCode-Solutions · MIT