900. RLE Iterator

RLE Iterator (LeetCode 900) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

How to solve RLE Iterator

RLE Iterator is a Data Structure Design problem, part of Design Patterns. Design and implement data structures: LRU cache, LFU cache, HashMap, and specialized structures.

Work towards the solution in these steps:

1. Think about how to maintain a pointer or index to track your current position in the run-length encoded array while iterating.
2. Consider updating the count of remaining elements for the current value as you exhaust elements, and move to the next run when the count reaches zero.
3. When the next(n) function is called, you may need to exhaust multiple runs; think about looping through runs until you've exhausted n elements or run out of runs.

The reference solution runs in O(L) time and O(L) space.

The RLE Iterator solution and editorial walks through the full approach with reference code.

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.

- For example, 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 <= 1000

- encoding.length is even.

- 0 <= encoding[i] <= 109

- 1 <= n <= 109

- At most 1000 calls will be made to next.

Topics and companies

Topics: Array, Design, Counting, Iterator.

Reported in interviews at Google.

How to practise RLE Iterator on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(L) time and O(L) space.

Open RLE Iterator in the code editor, or read the RLE Iterator editorial for a worked solution with its approach and complexity analysis.

Where RLE Iterator sits in the DSA pattern sheet

• Design Patterns pattern guide
• Design (General/Specific) subpattern
• The full DSA patterns sheet

Problems related to RLE Iterator

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

• All O`one Data Structure — Hard, same subpattern
• Design a Stack With Increment Operation — Medium, same subpattern
• Design a Text Editor — Hard, same subpattern
• Design Circular Deque — Medium, same subpattern
• Design Circular Queue — Medium, same subpattern
• Design Compressed String Iterator — Easy, same subpattern

RLE Iterator FAQ