RLE Iterator: Consuming a Run-Length Encoded Sequence

LeetCode 900, RLE Iterator, asks you to build an iterator over a run-length encoded sequence. You receive an encoding array and must support a next(n) operation that consumes the next n elements from the decoded sequence and returns the last one consumed.

The problem

You are given an even-length array encoding where encoding[2*i] is a count and encoding[2*i + 1] is a value. Together they describe a sequence: the value is repeated count times. For example, [3, 8, 0, 9, 2, 5] means "three 8s, zero 9s, two 5s", producing the decoded sequence [8, 8, 8, 5, 5].

You need to implement two operations:

• RLEIterator(encoding) initializes the iterator with the given encoding.
• next(n) exhausts the next n elements from the sequence and returns the value of the last element exhausted. If there are fewer than n elements remaining, return -1.

The brute force approach

The most obvious approach is to decode the entire sequence upfront. Loop through the encoding, and for each (count, value) pair, append the value to an array count times. Then next(n) just advances a pointer by n positions in that decoded array.

The problem? The counts can be enormous. A single pair like (10^9, 7) means one billion 7s. You cannot afford to store all of those in memory. The decoded sequence could be up to 10^9 elements long, while the encoding itself is at most 1000 elements.

The key insight

You do not need the decoded array at all. Instead, keep a pointer into the encoding and track how many elements remain in the current pair. When next(n) is called, subtract from the current pair's count. If the count runs out before you have consumed n, move the pointer to the next pair and keep subtracting.

Step-by-step walkthrough

The code

class RLEIterator:
    def __init__(self, encoding):
        self.encoding = encoding
        self.index = 0

    def next(self, n):
        while self.index < len(self.encoding):
            if self.encoding[self.index] >= n:
                self.encoding[self.index] -= n
                return self.encoding[self.index + 1]
            n -= self.encoding[self.index]
            self.encoding[self.index] = 0
            self.index += 2
        return -1

The constructor stores the encoding and sets a pointer index to 0, pointing at the first count.

When next(n) is called, you check the count at the current pointer. If it is large enough to satisfy n, subtract n from the count and return the corresponding value. If not, subtract the entire remaining count from n (consuming that segment completely), zero out the count, advance the pointer by 2 to the next pair, and repeat.

If you run out of pairs before consuming all n elements, return -1.

Complexity analysis

In the pointer approach, k is the number of pairs skipped during a single next call. Across all next calls combined, each pair is visited at most once, so the total work across all calls is O(n) where n is the length of the encoding. This makes each call O(1) amortized.

The space is O(1) extra because you only store the pointer index. The encoding itself is modified in place.

The building blocks

Pointer-based consumption

The core technique here is maintaining a pointer into a structured array and consuming elements without decoding. This pattern shows up whenever data is stored in a compressed or grouped format and you need to iterate lazily. Rather than expanding everything upfront, you track your position and consume on demand.

Amortized traversal

Even though a single next call might skip several pairs, the total number of pairs skipped across all calls is bounded by the encoding length. This amortized argument is the same one that justifies O(1) amortized cost for dynamic array resizing or two-pointer traversals where both pointers only move forward.

Edge cases

Zero counts. Some pairs have a count of 0 (like (0, 9) in our example). The algorithm handles these naturally: since the count is less than n, it subtracts 0 and moves to the next pair.

Exhausting the sequence. When next(n) requests more elements than remain, the pointer advances past the end of the encoding. Every subsequent call to next also returns -1 because the while loop condition fails immediately.

Single pair. If the encoding has just one pair, like [5, 3], repeated calls to next(1) return 3 five times and then -1 forever. The pointer never needs to advance past index 0 until the count hits 0.

Large n in one call. A single next call might consume across many pairs. The while loop handles this correctly by iterating through as many pairs as needed.

From understanding to recall

The idea behind this problem is clean: walk a pointer through pairs, subtract counts, return the value when you have consumed enough. When you read it here, every step makes sense. But in an interview, the details trip you up. Do you advance the pointer by 1 or by 2? Do you check >= or >? What do you do when a count is exactly 0?

These are the details that spaced repetition cements. You practice the pointer advancement loop as one brick, the count subtraction logic as another. After a few reps at increasing intervals, the while loop structure and the index += 2 pattern are automatic. You are not re-deriving the solution under pressure. You are assembling pieces you already know.

Pair this with related iterator problems like Peeking Iterator or Flatten Nested List Iterator, and you build a family of patterns around lazy, pointer-based iteration over structured data.

Related posts

• Peeking Iterator - Another iterator wrapper problem where you manage internal state to support look-ahead
• String Compression - Uses the same run-length encoding concept, but in reverse: compressing a character array in place
• Count and Say - Generates a sequence by repeatedly run-length encoding the previous term