Abstract / Summary

An iterator class efficiently traverses a run-length encoded sequence by repeating values according to their counts.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Counting
• Design
• Iterator

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The RLEIterator class implements an iterator over a run-length encoded (RLE) integer sequence. The constructor receives a flat list where each pair [count, value] represents count consecutive occurrences of value. The public method next(n) consumes n elements from the current position and returns the value of the element that would be observed at that position, or -1 if the iterator is exhausted.

Core Components

Initialization

def __init__(self, encoding: List[int]):
    self.rle = encoding
    self.pos = 0

The constructor stores the supplied encoding in self.rle and starts the cursor self.pos at the beginning of the list. No additional data structures are created, so the iterator works directly on the original list.

Primary Operation - next

def next(self, n: int) -> int:
    if self.pos == len(self.rle):
        return -1

The method first checks whether the cursor has already moved past the last element of the encoding. If so, it signals exhaustion by returning -1. This guard handles the edge case where a previous call consumed the entire sequence.

Consuming Within the Current Run

    if n <  self.rle[self.pos]:
        self.rle[self.pos] -= n
        return self.rle[self.pos + 1]

When the requested n is smaller than the remaining count at self.pos, the method decrements the stored count by n and returns the associated value (self.rle[self.pos + 1]). This updates the internal state so that subsequent calls continue from the correct offset inside the same run.

Exact Match of the Remaining Count

    if n == self.rle[self.pos]:
        self.pos += 2
        return self.rle[self.pos - 1]

If n exactly equals the remaining count, the entire current run is consumed. The cursor advances by two positions to skip both the count and its value, and the method returns the value that was just exhausted. This branch cleanly handles the boundary where a run ends precisely at the requested step.

Spanning Multiple Runs

    n -= self.rle[self.pos]
    self.pos += 2
    return self.next(n)

When n exceeds the remaining count, the method subtracts the current count from n, moves the cursor past the current pair, and recursively calls next with the reduced n. This recursion continues until one of the earlier branches resolves the request. The recursion naturally handles sequences that span an arbitrary number of runs without requiring explicit loops.

Edge Cases Addressed

• Empty Encoding - If the supplied list is empty, self.pos equals len(self.rle) from the start, and the first guard in next immediately returns -1.
• Exact Exhaustion - When a call to next consumes the final remaining count of the last run, the cursor moves beyond the list length, and subsequent calls are caught by the exhaustion guard.
• Large n Values - The recursive reduction of n allows the method to handle requests that are larger than any single run, correctly traversing multiple runs until the request is satisfied or the data ends.
• Repeated Calls - Because the count at each position is updated in place, successive calls to next correctly reflect the remaining elements without needing auxiliary bookkeeping.

Performance Optimizations

The implementation works directly on the original encoding list, mutating the count entries in place. This eliminates the need for auxiliary arrays or objects, keeping memory usage minimal. By adjusting self.rle[self.pos] rather than creating a new slice, the iterator avoids the overhead of copying data.

The use of a simple integer cursor (self.pos) to step through the list by increments of two provides constant-time access to both the count and its associated value. The recursive approach, while conceptually straightforward, leverages tail-like behavior: each recursive call processes a distinct run and immediately returns the result of the deeper call, avoiding additional processing after the recursive return. In practice, Python’s call stack depth is limited, but for typical RLE inputs the number of runs is modest, so the recursion remains efficient.

Overall, the design achieves a tight loop over the encoded data with minimal per-element work: a few integer comparisons, a subtraction, and an index lookup. This yields fast response for each next invocation while maintaining a compact internal state.

Imagine a line of colorful building blocks hidden inside a special box. Some blocks are red, some are blue, and some are yellow. Instead of listing every single block, the box keeps a secret list. It tells you how many blocks of one color are in a row, and then which color they are. For example, it might say three red blocks followed by two blue blocks.

The code acts like a tiny helper who manages the box. When you ask the helper for a certain number of blocks, the helper looks at the list of instructions. If the helper still has enough blocks of the current color, the helper just hands them over and keeps track of how many are left. If the helper runs out of that specific color, the helper simply moves to the very next instruction in the list and starts looking there instead. If there are no more blocks left in the box at all, the helper signals that it is empty. It is just like playing a game of taking items out of a bag one piece at a time until everything is gone.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java					TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java				Go	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	fengvyi	C++
	JoshCrozier					JS
	lkwq007		Python
	ruoru				Rust
	suxrobGM						C#
	varunu28			Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fengvyi	C++
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality