900. RLE Iterator

MediumDesignArrayCountingIterator
Leetcode Link

Problem Description

The problem presents a scenario where we are given a sequence of integers that has been encoded using the run-length encoding (RLE) technique. RLE is a simple form of data compression where sequences of the same data value are stored as a single data value and count. The encoded array, encoding, is an even-length array where for every even index i, encoding[i] represents the count of the following integer encoding[i + 1].

The objective is to implement an iterator for this RLE encoded sequence. Two operations need to be defined for this iterator:

  • RLEIterator(int[] encoded)- Constructor which initializes the RLEIterator with the encoded sequence.
  • int next(int n)- This method should simulate the iteration over n elements of the encoded sequence and return the value of the last element after exhausting n elements. If less than n elements are left, the iterator should return -1.

An example of how RLE works: if we have a sequence arr = [8, 8, 8, 5, 5], its RLE encoded form could be encoding = [3, 8, 2, 5], where [3, 8] means that 8 appears 3 times, and [2, 5] means that 5 appears 2 times.

Intuition

To tackle this problem, we need to simulate the decoding process of RLE on-the-fly, without actually generating the entire decoded sequence due to potentially high space requirements.

To design the RLEIterator class efficiently, we keep track of our current position in the encoded sequence with an index i, and also track the number of elements we have already 'seen' at the current index with curr. During the next(int n) operation, we need to exhaust n elements. There are two cases to consider:

  1. If the current count at encoding[i] is not enough to cover n (i.e., curr + n > encoding[i]), we know that we need to move to the next count-value pair by incrementing i by 2 and adjust n accordingly, taking into account the number of elements we have already exhausted with curr.

  2. If the current count can cover n, we simply add n to curr and return the value at encoding[i + 1], since n elements can be exhausted within the current count-value pair.

We repeat this process until we've either exhausted n elements and returned the last element exhausted, or we reach the end of the encoding array, where we return -1 to indicate there are no more elements to iterate through.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The solution makes use of a couple of important concepts: an index pointer and a count variable that together act as an iterator over the run-length encoded data. No additional data structure is required other than what's given by the encoding.

Here's a step-by-step breakdown of the RLEIterator implementation:

  1. The constructor __init__ simply initializes the encoding with the provided array. It also initializes two important variables: self.i, which represents the current index position in the encoding array (initially set to 0), and self.curr, which represents how many elements have been used up in the current run (initially set to 0).

  2. The next function is designed to handle the iteration through the encoded sequence:

    • We initiate a while loop that continues as long as self.i is within the bounds of the encoding array.
    • Inside the loop, we handle two scenarios regarding the provided n elements that we want to exhaust:
      • If the current run (self.encoding[self.i]) minus the number of elements already used (self.curr) is less than n, it means we need to move to the next run. We update n by subtracting the remaining elements of the current run and reset self.curr to 0, since we will move to the next run, and increment self.i by 2 to jump to the next run-length pair.
      • If the current run is enough to cover n, we update self.curr to include the exhausted elements n and return the value self.encoding[self.i + 1], which is the actual data value after using up n elements.
    • If we exit the loop, it means that all elements have been exhausted, and we return -1.

By incrementing only when necessary and by keeping track of how many elements we've 'seen' in the current run, we efficiently simulate the RLE sequence iteration.

No complex algorithms or data structures are needed, just careful indexing and counting, which keeps the space complexity to O(1) (aside from the input array) and the time complexity to O(n) in the worst case, where n is the total number of calls to next.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Example Walkthrough

Let's consider an encoded sequence encoding = [5, 3, 4, 2]. This means the number 3 appears 5 times followed by the number 2 appearing 4 times. If we translate that into its original sequence, it would look like [3, 3, 3, 3, 3, 2, 2, 2, 2]. We want to iterate over this sequence without actually decoding it.

Here is a step-by-step example illustrating the RLEIterator class functionality:

  1. We first initialize our iterator with the encoding array by calling the constructor: RLEIterator([5, 3, 4, 2]).

    • Our index i is set to 0, meaning we are at the start of our encoded array.
    • Our current run count curr is set to 0, meaning we have not used up any elements from the first run.
  2. We call the next function with n = 2: iterator.next(2).

    • We enter the while loop since i < len(encoding).
    • We check if the current run can accommodate n. Since encoding[0] - curr (5 - 0) is greater than 2, this run can accommodate it.
    • We update curr by adding n, now curr becomes 2.
    • We return the value 3 because it's the value associated with the current run.
  3. Now, let's consider iterator.next(5).

    • We check if the current run can accommodate n (5 in this case). The current curr is 2, so the remaining count in the current run is 3. Since 3 isn't enough to cover n=5, we exhaust this run and update n to n - (encoding[0] - curr) which is 5 - 3 = 2. Now we move to the next run by incrementing i by 2, so i is now 2, and reset curr to 0.
    • In the next iteration, we check if the next run can cover the remaining n=2. Since encoding[2] which is 4 is greater than 2, we can proceed.
    • We increment curr to curr + n which makes curr = 2, and we return encoding[i + 1] which is 2.
  4. If we keep calling next, eventually we would reach the end of the array. If i is no longer less than the length of encoding, it means we cannot return any more elements. In this case, iterator.next() would return -1.

By only moving to the next encoding pair when the current run is exhausted, and tracking the elements consumed in the curr variable, this implementation effectively iterates over the RLE sequence using a constant amount of extra space.

Not Sure What to Study? Take the 2-min Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Python Solution

1from typing import List
2
3class RLEIterator:
4    def __init__(self, encoding: List[int]):
5        self.encoding = encoding  # The run-length encoded array
6        self.index = 0            # Current index in the encoding array
7        self.offset = 0           # Offset to keep track of the current element count within the block
8
9    def next(self, n: int) -> int:
10        # Keep iterating until we find the n-th element or reach the end of the encoding
11        while self.index < len(self.encoding):
12            # If seeking past the current block
13            if self.offset + n > self.encoding[self.index]:
14                # Subtract the remaining elements of the current block from n
15                n -= self.encoding[self.index] - self.offset
16                # Reset the offset, and move to the next block (skip the value part of the block)
17                self.offset = 0
18                self.index += 2
19            else:
20                # The element is in the current block, so we update the offset
21                self.offset += n
22                # Return the value part of the current block
23                return self.encoding[self.index + 1]
24        # If we reached here, n is larger than the remaining elements
25        return -1
26
27
28# Example of how one would instantiate and use the RLEIterator class:
29# obj = RLEIterator(encoding)
30# element = obj.next(n)
31

Java Solution

1// RLEIterator decodes a run-length encoded sequence and supports
2// retrieving the next nth element.
3class RLEIterator {
4
5    private int[] encodedSequence; // This array holds the run-length encoded data.
6    private int currentIndex;      // Points to the current index of the encoded sequence.
7    private int currentCount;      // Keeps track of the count of the current element
8
9    // Constructs the RLEIterator with the given encoded sequence.
10    public RLEIterator(int[] encoding) {
11        this.encodedSequence = encoding;
12        this.currentCount = 0;
13        this.currentIndex = 0;
14    }
15
16    // Returns the element at the nth position in the decoded sequence or -1 if not present.
17    public int next(int n) {
18        // Iterates through the encodedSequence array.
19        while (currentIndex < encodedSequence.length) {
20            // If the current remainder of the sequence + n exceeds the current sequence value
21            if (currentCount + n > encodedSequence[currentIndex]) {
22                // Subtract the remainder of the current sequence from n
23                n -= encodedSequence[currentIndex] - currentCount;
24                // Move to the next sequence pair
25                currentIndex += 2;
26                // Reset currentCount for the new sequence
27                currentCount = 0;
28            } else {
29                // If n is within the current sequence count, add n to currentCount
30                currentCount += n;
31                // Return the corresponding element
32                return encodedSequence[currentIndex + 1];
33            }
34        }
35        // If no element could be returned, return -1 indicating the end of the sequence.
36        return -1;
37    }
38}
39
40// Usage:
41// RLEIterator iterator = new RLEIterator(new int[] {3, 8, 0, 9, 2, 5});
42// int element = iterator.next(2); // Should return the 2nd element in the decoded sequence.
43

C++ Solution

1#include <vector>
2
3// The RLEIterator class is used for Run Length Encoding (RLE) iteration.
4class RLEIterator {
5public:
6    // Store the encoded sequence
7    std::vector<int> encodedSequence;
8    // The current position in the encoded sequence
9    int currentCount;
10    // The index of the current sequence in the encoded vector
11    int currentIndex;
12
13    // Constructor that initializes the RLEIterator with an encoded sequence
14    RLEIterator(std::vector<int>& encoding) : encodedSequence(encoding), currentCount(0), currentIndex(0) {
15    }
16
17    // The next function returns the next element in the RLE sequence by advancing 'n' steps
18    int next(int n) {
19        // Keep iterating until we have processed all elements or until the end of the encoded sequence is reached
20        while (currentIndex < encodedSequence.size()) {
21            // If the steps 'n' exceed the number of occurrences of the current element
22            if (currentCount + n > encodedSequence[currentIndex]) {
23                // Deduct the remaining count of the current element from 'n'
24                n -= encodedSequence[currentIndex] - currentCount;
25                // Reset the current count as we move to the next element
26                currentCount = 0;
27                // Increment the index to move to the next element's occurrence count
28                currentIndex += 2;
29            } else {
30                // If 'n' is within the current element's occurrence count
31                currentCount += n;
32                // Return the current element's value
33                return encodedSequence[currentIndex + 1];
34            }
35        }
36        // Return -1 if there are no more elements to iterate over
37        return -1;
38    }
39};
40
41/*
42Exemplifying usage:
43std::vector<int> encoding = {3, 8, 0, 9, 2, 5};
44RLEIterator* iterator = new RLEIterator(encoding);
45int element = iterator->next(2); // Outputs the current element after 2 steps
46delete iterator; // Don't forget to deallocate the memory afterwards
47*/
48

Typescript Solution

1// Store the encoded sequence
2let encodedSequence: number[] = [];
3// The current position in the encoded sequence
4let currentCount: number = 0;
5// The index of the current sequence in the encoded vector
6let currentIndex: number = 0;
7
8/**
9 * Initializes the RLEIterator with an encoded sequence.
10 * @param encoding - The initial RLE encoded sequence.
11 */
12function initRLEIterator(encoding: number[]): void {
13    encodedSequence = encoding;
14    currentCount = 0;
15    currentIndex = 0;
16}
17
18/**
19 * The next function returns the next element in the RLE sequence by advancing 'n' steps.
20 * @param n - The number of steps to advance in the RLE sequence.
21 * @returns The value at the 'n'-th position or -1 if the sequence has been exhausted.
22 */
23function next(n: number): number {
24    // Continue iterating until all requested elements are processed or the end of the sequence is reached
25    while (currentIndex < encodedSequence.length) {
26        // If 'n' exceeds the occurrences of the current element
27        if (currentCount + n > encodedSequence[currentIndex]) {
28            // Subtract the remaining occurrences of the current element from 'n'
29            n -= encodedSequence[currentIndex] - currentCount;
30            // Reset the current count as we move to the next element
31            currentCount = 0;
32            // Move to the next element's occurrence count
33            currentIndex += 2;
34        } else {
35            // 'n' is within the current element's occurrence count
36            currentCount += n;
37            // Return the current element's value
38            return encodedSequence[currentIndex + 1];
39        }
40    }
41    // Return -1 if there are no more elements
42    return -1;
43}
44
45// Exemplifying usage:
46initRLEIterator([3, 8, 0, 9, 2, 5]);
47let element = next(2); // Outputs 8, since it's the current element after 2 steps
48
Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Time and Space Complexity

Time Complexity

The time complexity of the next method is O(K), where K is the number of calls to next, considering that at each call to the next method we process at most two elements from the encoding. In the worst case, we might traverse the entire encoding array once, processing two elements each time (the frequency and the value). The init method has a time complexity of O(1) since it only involves assigning the parameters to the instance variables without any iteration.

Space Complexity

The space complexity of the RLEIterator class is O(N), where N is the length of the encoding list. This is because we are storing the encoding in the instance variable self.encoding. No additional space is used that grows with the size of the input, as all other instance variables take up constant space.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫