RLE Iterator solution and explanation
Google
7 more videos on this problem
RLE Iterator | LeetCode 900 | List TreeMap | GoogleNaresh Gupta · 16:56 · 1K views
RLE IteratorScott · 5:24 · 887 views
Coding Interview Problem - RLE IteratorKnapsack · 13:01 · 731 views
RLE Iterator | Top Google Coding Interview QuestionCoding Courses · 11:19 · 727 views
900. RLE Iterator (Leetcode Medium)Programming Live with Larry · 9:51 · 574 views
LeetCode 900. RLE Iterator Solution Explained - JavaAlgorithms and Data Structures Course · 8:14 · 539 views
No Sound Leetcode 900: RLE IteratorExtremeProgrammer · 1:43 · 25 views
RLE IteratorOwen Wu · 3:19 · 6 views
The problem
We can use run-length encoding (i.e., RLE) to encode a sequence of integers. In a run-length encoded array of even length encoding (0-indexed), 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.
- For example, the sequence
arr = [8,8,8,5,5]can be encoded to beencoding = [3,8,2,5].encoding = [3,8,0,9,2,5]andencoding = [2,8,1,8,2,5]are also valid RLE ofarr.
Given a run-length encoded array, design an iterator that iterates through it.
Implement the RLEIterator class:
RLEIterator(int[] encoded)Initializes the object with the encoded arrayencoded.int next(int n)Exhausts the nextnelements and returns the last element exhausted in this way. If there is no element left to exhaust, return-1instead.
Example 1:
Input ["RLEIterator", "next", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]] Output [null, 8, 8, 5, -1] Explanation RLEIterator rLEIterator = new RLEIterator([3, 8, 0, 9, 2, 5]); // This maps to the sequence [8,8,8,5,5]. rLEIterator.next(2); // exhausts 2 terms of the sequence, returning 8. The remaining sequence is now [8, 5, 5]. rLEIterator.next(1); // exhausts 1 term of the sequence, returning 8. The remaining sequence is now [5, 5]. rLEIterator.next(1); // exhausts 1 term of the sequence, returning 5. The remaining sequence is now [5]. rLEIterator.next(2); // exhausts 2 terms, returning -1. This is because the first term exhausted was 5, but the second term did not exist. Since the last term exhausted does not exist, we return -1.
Constraints:
2 <= encoding.length <= 1000encoding.lengthis even.0 <= encoding[i] <= 1091 <= n <= 109- At most
1000calls will be made tonext.
Approach overview
Problem Overview: You are given a run-length encoded array where even indices store a frequency and the next index stores the value. The iterator must consume elements from this compressed representation and return the value of the last element exhausted after calling next(n). If fewer than n elements remain, return -1.
Approach 1: Fully Decompress the Array (O(N) time, O(N) space)
The most straightforward idea is to rebuild the original array from the run-length encoding. Iterate through the encoded list two elements at a time: the first is the count and the second is the value. Append the value count times into a new array, then maintain a pointer that advances when next(n) is called. Each query simply moves the pointer forward by n and returns the value at the final consumed index. This approach is easy to reason about but inefficient when counts are large because the decompressed array may contain millions of elements.
Approach 2: Index + Remaining Count in Encoding (O(1) amortized time, O(1) space)
The optimal solution works directly on the encoded structure without expanding it. Maintain an index pointing to the current frequency in the encoding array and treat that frequency as the number of remaining elements in the current run. When next(n) is called, repeatedly consume from the current run: if the remaining count is smaller than n, subtract it from n and move the index forward to the next run. Otherwise reduce the current count by n and return the associated value. This effectively simulates iteration while keeping the data compressed.
The key insight is that each run is processed only once. Even if a single next call skips multiple runs, the pointer never moves backward. Across all operations, each encoded segment is visited at most once, giving O(1) amortized time per call and O(1) extra space. This fits naturally with iterator-style problems and is common in design questions.
The encoding array itself acts as a compact structure storing counts and values, which makes the logic closely related to array traversal and frequency management patterns often seen in counting problems. The iterator simply tracks how many elements of the current run remain before moving to the next pair.
Recommended for interviews: The index-and-offset technique is what interviewers expect. It demonstrates that you understand how run-length encoding works and how to iterate over compressed data without expanding it. Mentioning the decompression idea first shows baseline reasoning, but implementing the in-place encoded traversal proves stronger algorithmic design skills.
Approach 1: Utilize an Index and Offset in Encoding
This approach involves keeping track of the current position in the encoding list using an index. The goal is to iteratively exhaust elements as specified until the required number of elements 'n' is exhausted. We make use of an offset to track how many elements of the current run-length have been consumed. When moving past a run-length, we update the index to the next pair in the encoding list, and reset the offset.
class RLEIterator:
def __init__(self, encoding: list):
self.encoding = encoding
self.index = 0
self.offset = 0
def next(self, n: int) -> int:
while self.index < len(self.encoding):
if self.offset + n > self.encoding[self.index]:
n -= (self.encoding[self.index] - self.offset)
self.index += 2
self.offset = 0
else:
self.offset += n
return self.encoding[self.index + 1]
return -1class RLEIterator {
private int[] encoding;
private int index;
private int offset;
public RLEIterator(int[] encoding) {
this.encoding = encoding;
this.index = 0;
this.offset = 0;
}
public int next(int n) {
while (index < encoding.length) {
if (offset + n > encoding[index]) {
n -= (encoding[index] - offset);
index += 2;
offset = 0;
} else {
offset += n;
return encoding[index + 1];
}
}
return -1;
}
}class RLEIterator {
public:
RLEIterator(vector<int>& encoding) : encoding(encoding), index(0), offset(0) {}
int next(int n) {
while (index < encoding.size()) {
if (offset + n > encoding[index]) {
n -= (encoding[index] - offset);
index += 2;
offset = 0;
} else {
offset += n;
return encoding[index + 1];
}
}
return -1;
}
private:
vector<int>& encoding;
int index;
int offset;
};class RLEIterator {
constructor(encoding) {
this.encoding = encoding;
this.index = 0;
this.offset = 0;
}
next(n) {
while (this.index < this.encoding.length) {
if (this.offset + n > this.encoding[this.index]) {
n -= (this.encoding[this.index] - this.offset);
this.index += 2;
this.offset = 0;
} else {
this.offset += n;
return this.encoding[this.index + 1];
}
}
return -1;
}
}#include <stdlib.h>
typedef struct {
int* encoding;
int index;
int offset;
} RLEIterator;
RLEIterator* rLEIteratorCreate(int* encoding, int encodingSize) {
RLEIterator* obj = (RLEIterator*) malloc(sizeof(RLEIterator));
obj->encoding = encoding;
obj->index = 0;
obj->offset = 0;
return obj;
}
int rLEIteratorNext(RLEIterator* obj, int n) {
while (obj->index < obj->encodingSize) {
if (obj->offset + n > obj->encoding[obj->index]) {
n -= (obj->encoding[obj->index] - obj->offset);
obj->index += 2;
obj->offset = 0;
} else {
obj->offset += n;
return obj->encoding[obj->index + 1];
}
}
return -1;
}
void rLEIteratorFree(RLEIterator* obj) {
free(obj);
}public class RLEIterator {
private int[] encoding;
private int index;
private int offset;
public RLEIterator(int[] encoding) {
this.encoding = encoding;
this.index = 0;
this.offset = 0;
}
public int Next(int n) {
while (index < encoding.Length) {
if (encoding[index] - offset < n) {
n -= (encoding[index] - offset);
index += 2;
offset = 0;
} else {
offset += n;
return encoding[index + 1];
}
}
return -1;
}
}In the given Python solution, the RLEIterator class is initialized with the run-length encoded array, and maintains a counter to keep the track of current index and offset in the array. Each call to the next(n) method exhausts n elements by iterating through the encoding array and either returns the current value exhausted or -1 if all elements are already consumed.
Time Complexity: O(m), where m is the number of elements needed to exhaust until n is reached.
Space Complexity: O(1), since no additional space is used apart from a few variables.
Approach 2: Maintain Two Pointers
We define two pointers i and j, where pointer i points to the current run-length encoding being read, and pointer j points to which character in the current run-length encoding is being read. Initially, i = 0, j = 0.
Each time we call next(n), we judge whether the remaining number of characters in the current run-length encoding encoding[i] - j is less than n. If it is, we subtract n by encoding[i] - j, add 2 to i, and set j to 0, then continue to judge the next run-length encoding. If it is not, we add n to j and return encoding[i + 1].
If i exceeds the length of the run-length encoding and there is still no return value, it means that there are no remaining elements to be exhausted, and we return -1.
The time complexity is O(n + q), and the space complexity is O(n). Here, n is the length of the run-length encoding, and q is the number of times next(n) is called.
class RLEIterator {
private encoding: number[];
private i: number;
private j: number;
constructor(encoding: number[]) {
this.encoding = encoding;
this.i = 0;
this.j = 0;
}
next(n: number): number {
while (this.i < this.encoding.length) {
if (this.encoding[this.i] - this.j < n) {
n -= this.encoding[this.i] - this.j;
this.i += 2;
this.j = 0;
} else {
this.j += n;
return this.encoding[this.i + 1];
}
}
return -1;
}
}
/**
* Your RLEIterator object will be instantiated and called as such:
* var obj = new RLEIterator(encoding)
* var param_1 = obj.next(n)
*/type RLEIterator struct {
encoding []int
i, j int
}
func Constructor(encoding []int) RLEIterator {
return RLEIterator{encoding, 0, 0}
}
func (this *RLEIterator) Next(n int) int {
for this.i < len(this.encoding) {
if this.encoding[this.i]-this.j < n {
n -= (this.encoding[this.i] - this.j)
this.i += 2
this.j = 0
} else {
this.j += n
return this.encoding[this.i+1]
}
}
return -1
}
/**
* Your RLEIterator object will be instantiated and called as such:
* obj := Constructor(encoding);
* param_1 := obj.Next(n);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Utilize an Index and Offset in Encoding | Time Complexity: O(m), where m is the number of elements needed to exhaust until |
| Maintain Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Fully Decompress the Array | O(N) | O(N) | Simple implementation when encoded counts are small and memory is not a concern |
| Index and Remaining Count in Encoding | O(1) amortized per call | O(1) | Best choice for large counts and interview settings where the array must remain compressed |
Frequently asked questions
Is RLE Iterator easy or hard?
RLE Iterator is generally classified as a medium difficulty problem. The main challenge is recognizing that you should simulate iteration over the compressed representation instead of decompressing the entire array.
RLE Iterator Python/Java solution
Both Python and Java implementations keep an index pointing to the frequency in the encoding array and decrement it as elements are consumed. When the frequency reaches zero, the pointer moves to the next pair. This produces an O(1) amortized next(n) operation without expanding the encoded sequence.
How to solve RLE Iterator in O(n)?
Iterate directly over the encoded array while maintaining the remaining frequency of the current run. When next(n) is requested, subtract from the current count until either the request is satisfied or the run is exhausted. Move to the next encoded pair when needed. Each encoded segment is visited once, giving linear work across the lifetime of the iterator.
What is the best approach for RLE Iterator?
The optimal approach keeps a pointer inside the run-length encoded array and consumes counts directly instead of decompressing the data. Track the current run index and decrease its remaining frequency whenever next(n) is called. If the run is exhausted, move to the next pair. This gives O(1) amortized time per operation and O(1) extra space.
Is RLE Iterator asked at Google/Amazon/Meta?
RLE Iterator is a classic design-style problem similar to questions used in interviews at companies like Google, Amazon, and Meta. It tests your ability to build iterators over compressed data structures and reason about amortized complexity.
What data structure is used in RLE Iterator?
The solution primarily uses an array storing run-length encoded pairs and a pointer that tracks the current run. The iterator logic manipulates counts directly, which makes the array act like a compressed stream of values.
What is the time complexity of RLE Iterator?
Using the index-and-count approach, each run in the encoding is processed at most once. Although a single next(n) call might skip several runs, the total work across all calls is linear in the number of encoded pairs. The amortized complexity per operation is O(1) with O(1) additional space.