Scale Engineer

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
DesignCountingIterator
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] <= 109
  • 1 <= n <= 109
  • 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.
import java.util.ArrayList;import java.util.List; class RLEIterator {    private List<Long> decompressed;    private int index;     public RLEIterator(int[] encoding) {        // Note: Using Long for counts to avoid overflow, though List size is limited by Integer.MAX_VALUE        // This approach is fundamentally flawed by memory limits regardless.        this.decompressed = new ArrayList<>();        this.index = 0;        for (int i = 0; i < encoding.length; i += 2) {            long count = encoding[i];            int value = encoding[i + 1];            for (long j = 0; j < count; j++) {                // This loop is the source of the TLE/MLE                this.decompressed.add((long)value);            }        }    }     public int next(int n) {        if (this.index + n > this.decompressed.size()) {            this.index = this.decompressed.size(); // Exhaust all remaining            return -1;        }        this.index += n;        return this.decompressed.get(this.index - 1).intValue();    }}

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.

Solutions

class 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); */

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 →

Next problem