RLE Iterator

Med

#0854Time: O(S) for the constructor, where S is the total number of elements in the decompressed sequence. Each `next(n)` call is O(1). The high cost of the constructor makes this approach inefficient.Space: O(S), where S is the total number of elements in the decompressed sequence (i.e., the sum of all counts in the `encoding` array). This can be extremely large.

Patterns

Design Counting Iterator

Data structures

Array

Prompt

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] <= 10⁹
1 <= n <= 10⁹
At most 1000 calls will be made to next.

Approaches

2 approaches with complexity analysis and trade-offs.

This brute-force approach involves pre-processing the run-length encoded array by fully decompressing it into the actual sequence of numbers. The constructor builds a large list containing every number in the sequence. The next method then simply advances a pointer through this pre-built list to find the required element.

Algorithm

Initialization: In the constructor, create a new list to hold the decompressed sequence and an index to track the current position.
Decompression: Iterate through the encoding array. For each pair (count, value), add value to the list count times. This happens once during initialization.
next(n) Call:
- Calculate the target position by adding n to the current index.
- Check if the target position is beyond the bounds of the decompressed list.
- If it is, there are not enough elements. Update the index to the end of the list and return -1.
- If there are enough elements, update the index to the target position and return the element at index - 1.

Walkthrough

The RLEIterator class maintains the entire expanded sequence in a list (e.g., ArrayList in Java) and a pointer or index to the current position in this sequence.

Constructor (RLEIterator(int[] encoding)):

It initializes an empty list.
It then iterates through the input encoding array, taking elements two at a time. For each pair (count, value), it adds the value to the list count times.
This process fully expands the run-length encoded data into a standard sequence, which is stored for later use.
An index, say cursor, is initialized to 0.

next(int n) Method:

This method simulates moving n steps forward in the decompressed list.
It checks if moving n steps from the current cursor position will go past the end of the list (cursor + n > list.size()).
If it does, it means we cannot exhaust n elements. The iterator exhausts all remaining elements, and as per the problem, returns -1.
Otherwise, it advances the cursor by n and returns the element at the new position minus one (list.get(cursor - 1)), which is the last element exhausted.

1import java.util.ArrayList;2import java.util.List;3 4class RLEIterator {5    private List<Long> decompressed;6    private int index;7 8    public RLEIterator(int[] encoding) {9        // Note: Using Long for counts to avoid overflow, though List size is limited by Integer.MAX_VALUE10        // This approach is fundamentally flawed by memory limits regardless.11        this.decompressed = new ArrayList<>();12        this.index = 0;13        for (int i = 0; i < encoding.length; i += 2) {14            long count = encoding[i];15            int value = encoding[i + 1];16            for (long j = 0; j < count; j++) {17                // This loop is the source of the TLE/MLE18                this.decompressed.add((long)value);19            }20        }21    }22 23    public int next(int n) {24        if (this.index + n > this.decompressed.size()) {25            this.index = this.decompressed.size(); // Exhaust all remaining26            return -1;27        }28        this.index += n;29        return this.decompressed.get(this.index - 1).intValue();30    }31}

Complexity

Time

O(S) for the constructor, where S is the total number of elements in the decompressed sequence. Each `next(n)` call is O(1). The high cost of the constructor makes this approach inefficient.

Space

O(S), where S is the total number of elements in the decompressed sequence (i.e., the sum of all counts in the `encoding` array). This can be extremely large.

Trade-offs

Pros

The logic is straightforward and easy to understand.
Once the initial decompression is done, each next(n) call is very fast, operating in constant time.

Cons

The constructor's time complexity is proportional to the total number of elements in the sequence (S), which can be enormous (1000 * 10^9), leading to a Time Limit Exceeded (TLE) error.
The space complexity is also O(S), which will almost certainly cause a Memory Limit Exceeded (MLE) error given the constraints.
This approach is not feasible for the problem's constraints.

This optimal approach avoids the massive memory and time costs of decompression by working with the encoding array directly. It uses a pointer to keep track of the current position in the encoded data. When next(n) is called, it iterates through the encoded pairs, consuming elements on-the-fly until n elements have been exhausted.

Algorithm

Initialization: Store the encoding array and an index pointer, ptr, initialized to 0.
next(n) Call:
- Loop as long as the pointer ptr is within the bounds of the encoding array.
- Let count be encoding[ptr] and value be encoding[ptr + 1].
- Case 1: n <= count (The current group has enough elements).
  - Decrease the group's count by n: encoding[ptr] -= n.
  - The last element exhausted is value, so return it.
- Case 2: n > count (The current group is not enough).
  - Exhaust the entire current group. Decrease n by count: n -= encoding[ptr].
  - Move the pointer to the next group: ptr += 2.
Termination: If the loop finishes (i.e., ptr goes out of bounds) without returning a value, it means there were not enough elements in the entire sequence to satisfy the next(n) call. Return -1.

Walkthrough

Instead of creating a new, potentially huge, data structure, this method cleverly uses the input encoding array itself to maintain the state of the iterator. It only needs one extra piece of information: an index or pointer to the current group (count, value) it is processing.

State:

int[] encoding: The run-length encoded array.
int index: A pointer to the start of the current group in the encoding array (always an even number).

Constructor (RLEIterator(int[] encoding)):

It simply stores a reference to the encoding array and initializes the index pointer to 0. This is a very fast O(1) operation.

next(int n) Method:

The method enters a loop that continues as long as there are groups left to process (index < encoding.length).
Inside the loop, it looks at the current group's count, encoding[index].
If n is smaller than or equal to the current count, it means the group has enough elements to satisfy the request. The last element exhausted will be the value of this group, encoding[index + 1]. We subtract n from the count (encoding[index] -= n) to reflect the consumption and return the value.
If n is larger than the current count, the entire group is consumed. We subtract the count from n (n -= encoding[index]) and advance our index by 2 to move to the next group.
If the loop completes, it means we have traversed all the groups but still couldn't exhaust n elements. In this case, we return -1.

1class RLEIterator {2    private int[] encoding;3    private int index;4 5    public RLEIterator(int[] encoding) {6        this.encoding = encoding;7        this.index = 0;8    }9 10    public int next(int n) {11        while (index < encoding.length) {12            // If the current group has enough elements to satisfy the request13            if (n <= encoding[index]) {14                encoding[index] -= n;15                return encoding[index + 1];16            }17            18            // Otherwise, the current group is not enough.19            // Exhaust the current group and move to the next.20            n -= encoding[index];21            index += 2;22        }23        24        // If the loop finishes, we've run out of elements in the sequence.25        return -1;26    }27}

Complexity

Time

O(N) for all calls to `next` combined, where N is the length of the `encoding` array. The `index` pointer only moves forward, so it will traverse the array at most once across all calls. The constructor is O(1).

Space

O(1) extra space, as it only stores a pointer. It modifies the input array in-place.

Trade-offs

Pros

Extremely efficient in terms of space, using only O(1) extra space.
Efficient in time. The total work done across all next calls is proportional to the length of the encoding array, not the size of the decompressed sequence.
It's the optimal solution for the given constraints.

Cons

This approach modifies the input encoding array. If the original array must be preserved, a copy should be made in the constructor, which would increase the space complexity to O(N), where N is the length of the encoding array.

Solutions

Solution

1class RLEIterator { private int [] encoding ; private int i ; private int j ; public RLEIterator ( int [] encoding ) { this . encoding = encoding ; } public int next ( int n ) { while ( i < encoding . length ) { if ( encoding [ i ] - j < n ) { n -= ( encoding [ i ] - j ); i += 2 ; j = 0 ; } else { j += n ; return encoding [ i + 1 ]; } } return - 1 ; } } /** * Your RLEIterator object will be instantiated and called as such: * RLEIterator obj = new RLEIterator(encoding); * int param_1 = obj.next(n); */

1class RLEIterator { public: RLEIterator ( vector < int >& encoding ) { this -> encoding = encoding ; } int next ( int n ) { while ( i < encoding . size ()) { if ( encoding [ i ] - j < n ) { n -= ( encoding [ i ] - j ); i += 2 ; j = 0 ; } else { j += n ; return encoding [ i + 1 ]; } } return - 1 ; } private: vector < int > encoding ; int i = 0 ; int j = 0 ; }; /** * Your RLEIterator object will be instantiated and called as such: * RLEIterator* obj = new RLEIterator(encoding); * int param_1 = obj->next(n); */

1class 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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem