RLE Iterator — Solution in Python, Java & C++
RLE Iterator solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Google.
RLE Iterator is a medium coding problem on arrays and counting, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Counting
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A sequence of integers can be stored compactly with run-length encoding: an even-length array encoding where, for every even index i, the value encoding[i + 1] appears encoding[i] times in a row. For example [3,8,0,9,2,5] stands for [8,8,8,5,5] — three 8s, no 9s, two 5s. A run with a count of 0 contributes nothing.
Write the class RLEIterator that walks such a sequence without expanding it:
RLEIterator(int[] encoding)starts at the beginning of the sequence thatencodingdescribes.int next(int n)consumes the nextnelements and returns the last one consumed. If fewer thannelements are left, it consumes all of them and returns-1.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
Example 1
Input: ["RLEIterator","next","next","next","next"]
[[[2,4,0,7,3,1]],[1],[2],[2],[1]]
Output: [null,4,1,1,-1]
Explanation: The sequence is [4,4,1,1,1]. next(1) consumes one 4 and returns 4. next(2) consumes the other 4 and a 1, returning 1. Only one 1 is left, so next(2) consumes it and returns -1; after that nothing remains and next(1) is -1 too.
Example 2
Input: ["RLEIterator","next","next","next"]
[[[0,9,1000000000,5]],[999999999],[1],[1]]
Output: [null,5,5,-1]
Explanation: The run of 9s is empty. The sequence is a billion 5s: the first call consumes all but one and returns 5, the second consumes the last 5, and the third finds nothing left.
Constraints
2 <= encoding.length <= 1000encoding.length is even0 <= encoding[i] <= 10^91 <= n <= 10^9At most 1000 calls are made to next
Hints for RLE Iterator
Hint 1
The counts can be a billion, so the sequence can never be written out. Work with the runs themselves.
Hint 2
Keep a pointer to the current run and treat its count as "how many of this value are still unread".
Hint 3
For
next(n): whilenis larger than the current run's remaining count, subtract that count fromnand move to the next run. If you run out of runs, return -1; otherwise takenfrom the current run and return its value.
How to solve RLE Iterator
Never expand the encoding. Keep a pointer i to the current run and let encoding[i] mean "elements of this run not yet consumed"; a call to next eats whole runs until the remainder fits inside one.
Approach
- Copy the encoding and set
i = 0. next(n): whileiis inside the array andn > encoding[i], don -= encoding[i]andi += 2— that run is used up entirely (empty runs pass through here too).- If
iran past the end, fewer thannelements were left: return -1 (they are all consumed now, so every later call returns -1 as well). - Otherwise
n <= encoding[i]: subtractnfrom the run and return its valueencoding[i + 1].
Why it works
The loop consumes exactly the elements before the one that ends this call: a run is skipped only when all of it is needed, and the call stops in the first run that still holds at least n elements, whose value is therefore the last element consumed. Leaving the remainder in encoding[i] makes the next call start exactly where this one stopped.
Complexity
- Time —
O(r + q) over the whole session for r runs and q calls — the pointer only moves forward - Space —
O(r) for the copy
Pitfalls
- Expanding the runs into a list runs out of memory: a single count can be 10^9.
- The comparison is
n > count, not>=: whennequals the remaining count, the call ends inside this run and returns its value. - After a call returns -1 the iterator is exhausted; the pointer is already past the end, so nothing extra is needed.
Reference solution
Python
class RLEIterator:
def __init__(self, encoding: List[int]):
self.enc = list(encoding)
self.i = 0
def next(self, n: int) -> int:
enc = self.enc
while self.i < len(enc) and n > enc[self.i]:
n -= enc[self.i] # this whole run is consumed
self.i += 2
if self.i >= len(enc):
return -1
enc[self.i] -= n
return enc[self.i + 1]Java
class RLEIterator {
private int[] enc;
private int i = 0;
public RLEIterator(int[] encoding) {
enc = encoding.clone();
}
public int next(int n) {
while (i < enc.length && n > enc[i]) {
n -= enc[i]; // this whole run is consumed
i += 2;
}
if (i >= enc.length) return -1;
enc[i] -= n;
return enc[i + 1];
}
}C++
class RLEIterator {
vector<int> enc;
size_t i = 0;
public:
RLEIterator(vector<int>& encoding) : enc(encoding) {}
int next(int n) {
while (i < enc.size() && n > enc[i]) {
n -= enc[i]; // this whole run is consumed
i += 2;
}
if (i >= enc.size()) return -1;
enc[i] -= n;
return enc[i + 1];
}
};JavaScript
var RLEIterator = function(encoding) {
this.enc = encoding.slice();
this.i = 0;
};
RLEIterator.prototype.next = function(n) {
var enc = this.enc;
while (this.i < enc.length && n > enc[this.i]) {
n -= enc[this.i]; // this whole run is consumed
this.i += 2;
}
if (this.i >= enc.length) return -1;
enc[this.i] -= n;
return enc[this.i + 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays