Leetcode #900: RLE Iterator
In this guide, we solve Leetcode #900 RLE Iterator in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Design, Array, Counting, Iterator
Intuition
The output depends on how often values appear.
Counting frequencies lets us answer queries in constant time afterward.
Approach
Count occurrences with a map or array, then compute the result from those counts.
This avoids repeated scans of the input.
Steps:
- Count frequencies.
- Use counts to compute result.
- Return the computed value.
Example
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.
Python Solution
class RLEIterator:
def __init__(self, encoding: List[int]):
self.encoding = encoding
self.i = 0
self.j = 0
def next(self, n: int) -> int:
while self.i < len(self.encoding):
if self.encoding[self.i] - self.j < n:
n -= self.encoding[self.i] - self.j
self.i += 2
self.j = 0
else:
self.j += n
return self.encoding[self.i + 1]
return -1
# Your RLEIterator object will be instantiated and called as such:
# obj = RLEIterator(encoding)
# param_1 = obj.next(n)
Complexity
The time complexity is , and the space complexity is . The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.