Watch 10 video solutions for RLE Iterator, a medium level problem involving Array, Design, Counting. This walkthrough by Naresh Gupta has 1,837 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |