900. RLE Iterator

Problem¶

Design an iterator over [count, value, ...]. Each next(n) consumes n elements and returns the last consumed value, or -1 if fewer than n remain. A failed call still exhausts the remaining elements.

encoding = [3, 8, 0, 9, 2, 5]  →  [8, 8, 8, 5, 5]

Call       Return   Remaining
next(2)       8     [8, 5, 5]
next(1)       8     [5, 5]
next(1)       5     [5]
next(2)      -1     []

class RLEIterator:
    def __init__(self, encoding: list[int]):
        pass

    def next(self, n: int) -> int:
        pass

Key trick¶

Track the current run and how much of it has been consumed; skip entire runs rather than individual elements.

Trap¶

Zero-length runs must be skipped, consuming exactly a run's remaining count must return its value, and an oversized request must leave the iterator exhausted.

Why is it interesting?¶

It tests stateful API design and amortized analysis: large counts are inexpensive because each run is passed at most once.

Python solution¶

class RLEIterator:
    def __init__(self, encoding: list[int]):
        self.encoding = encoding
        self.i = 0
        self.used = 0

    def next(self, n: int) -> int:
        while self.i < len(self.encoding):
            rem = self.encoding[self.i] - self.used

            if n <= rem:
                # Equality still returns this run's value.
                self.used += n
                return self.encoding[self.i + 1]

            # Consume this run, including zero-length runs.
            n -= rem
            self.i += 2
            self.used = 0

        return -1

For \(k\) encoded runs and \(q\) calls:

Time: \(O(k)\) worst case per call; \(O(k + q)\) across all calls.
Auxiliary space: \(O(1)\); the input is neither copied nor expanded.

Comment on my solution¶

Your solution is correct, including zero-length runs, exact boundaries, and exhaustion after oversized requests. It has the same complexity as the solution above and does not modify the input.

The main simplification is removing cached val and _hasnext(): the current value is available directly from the encoding. _hasnext() can return True when only zero-length runs remain, but your loop handles that correctly.

# WORKS
class RLEIterator:
    def __init__(self, encoding: list[int]):
        self.encoding = encoding
        self.i = 0
        self.cnt = 0
        self.val = None

    def _hasnext(self):
        return self.cnt > 0 or self.i < len(self.encoding)

    def next(self, n: int) -> int:
        while n > 0 and self._hasnext():
            if self.cnt >= n:
                self.cnt -= n
                return self.val
            else:
                n -= self.cnt
                self.cnt = 0
                self.val = None
            if self.i < len(self.encoding):
                self.cnt = self.encoding[self.i]
                self.val = self.encoding[self.i + 1]
                self.i += 2
        return -1