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.
arr = [8,8,8,5,5] can be encoded to be encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] and encoding = [2,8,1,8,2,5] are also valid RLE of arr.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 array encoded.int next(int n) Exhausts the next n elements and returns the last element exhausted in this way. If there is no element left to exhaust, return -1 instead.
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.length is even.0 <= encoding[i] <= 1091 <= n <= 1091000 calls will be made to next.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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
RLE Iterator | LeetCode 900 | List TreeMap | Google • Naresh Gupta • 1,837 views views
Watch 9 more video solutions →Practice RLE Iterator with our built-in code editor and test cases.
Practice on FleetCode