{x}
blog image

RLE Iterator

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.

Solution Explanation: RLE Iterator

This problem involves designing an iterator for a Run-Length Encoded (RLE) array. RLE is a data compression technique where consecutive runs of the same value are represented by a pair: (count, value). The RLEIterator class needs to efficiently handle requests for the next n elements from this compressed representation.

Approach:

The most efficient approach uses two pointers:

  • i: Index to track the current (count, value) pair in the encoding array. We increment i by 2 to move to the next pair.
  • j: Index to keep track of how many elements have been consumed within the current pair.

The next(n) method iteratively consumes n elements:

  1. Check Remaining Elements: It first checks if the remaining elements in the current run (encoding[i] - j) are sufficient to fulfill the request for n elements.
  2. Insufficient Elements: If not enough elements are available in the current run, it updates n by subtracting the remaining elements of the current run and moves to the next pair by incrementing i by 2 and resetting j to 0. This process continues until either n becomes 0 or we run out of pairs.
  3. Sufficient Elements: If the current run has enough elements, it updates j by n, effectively consuming n elements, and returns the value associated with the current pair (encoding[i + 1]).
  4. No More Elements: If we reach the end of the encoding array (i >= encoding.length) and still haven't fulfilled the request, it means there are no more elements, so it returns -1.

Time and Space Complexity:

  • Time Complexity: The time complexity of next(n) is O(k), where k is the number of pairs we need to traverse before fulfilling the request for n elements. In the worst case, k could be proportional to the length of the encoding array. However, it's amortized O(1) because each next call consumes elements, and we don't repeatedly process the same pairs. The overall time complexity considering multiple next calls is still bound by the number of elements processed (which is at most the sum of all counts in the encoding).
  • Space Complexity: The space complexity is O(1) because we are only using a fixed number of variables (i, j) regardless of the input size.

Code Examples (Python):

class 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:
                self.j += n
                return self.encoding[self.i + 1]
            else:
                n -= (self.encoding[self.i] - self.j)
                self.i += 2
                self.j = 0
        return -1

The other language examples (Java, C++, Go, TypeScript) follow the same logic, just with syntax variations specific to each language. Refer to the detailed code in the original response for these implementations.