RLE Iterator

Medium

Asked by:

21 views

Topics:

Arrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input `encoding` array ever be empty or null?
What is the range of values for the `quantity` and `value` pairs in the `encoding` array? Can they be zero or negative?
If `next(n)` is called with an `n` larger than the total number of elements represented by the encoding, what should be returned?
Is it possible for the `encoding` array to have consecutive runs with the same value, and how should I handle that?
Is the `encoding` array guaranteed to have an even number of elements, representing valid `quantity, value` pairs?

Brute Force Solution

Approach

Imagine you have a series of numbers representing how many times to repeat some values. The brute force approach is like going through the repetitions one by one, manually subtracting from the counts as you use them. If you run out of repetitions or values, you simply stop.

Here's how the algorithm would work step-by-step:

Look at the first number-value pair. The number tells you how many times to provide the value.
If you need to provide fewer values than the number available, subtract the amount you need from the number and return the value.
If you need to provide more values than the number available, return the value as many times as indicated by the number, and then move on to the next number-value pair.
Repeat the process with the subsequent number-value pairs, subtracting from the numbers until you've provided enough values or you run out of number-value pairs.
If you run out of number-value pairs before providing enough values, indicate that there are no more values to provide.

Code Implementation

class RLEIterator:

    def __init__(self, encoding):
        self.encoding = encoding
        self.current_index = 0

    def next(self, number_needed):
        # Iterate while we still need numbers
        while number_needed > 0:
            # Check if we've run out of encoding pairs
            if self.current_index >= len(self.encoding):
                return -1

            count = self.encoding[self.current_index]
            value = self.encoding[self.current_index + 1]

            # Enough elements available
            if count >= number_needed:
                self.encoding[self.current_index] -= number_needed

                # Return the value, decrement number_needed
                result = value
                number_needed = 0

                return result

            # Not enough elements available; consume all
            else:
                # Reduce needed count by the current count
                number_needed -= count

                # Move to next pair
                self.current_index += 2

        return result

Big(O) Analysis

Time Complexity

O(n) – The next() function iterates through the encoding array in the worst case once. The number of steps is proportional to the number of pairs in the input array. Therefore, the time complexity is O(n), where n is the number of pairs (run-length and value) in the input.

Space Complexity

O(1) – The RLE iterator, as described, processes the input series of numbers and values in place. It only needs to keep track of the current index or pointer within the input, and potentially a count of remaining repetitions. These variables require constant extra space, independent of the input size N (the number of number-value pairs). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The RLE Iterator problem requires us to virtually expand a compressed sequence on demand. Instead of actually expanding the entire sequence, we will keep track of our current position within the compressed data and only expand enough to fulfill each requested quantity.

Here's how the algorithm would work step-by-step:

First, keep track of which number-character pair you're currently working with in the compressed sequence.
When asked for a certain quantity of characters, check if the current number-character pair has enough characters to satisfy the request.
If it does, subtract the requested quantity from the current number, and return the character repeated that many times.
If it doesn't, return as many characters as the current number indicates, set the current number to zero, and move to the next number-character pair. Repeat until the requested quantity is fulfilled or the compressed sequence is exhausted.
If the compressed sequence is exhausted before the requested quantity is fulfilled, return nothing.
By only processing as many characters as needed for each request and advancing through the compressed data, you avoid expanding the entire sequence upfront, which improves efficiency.

Code Implementation

class RLEIterator:

    def __init__(self, encoding: list[int]):
        self.encoding = encoding
        self.current_index = 0

    def next(self, number_of_elements: int) -> int:
        remaining_elements = number_of_elements

        # Iterate as long as there are elements to provide
        while remaining_elements > 0:
            # Sequence exhausted, return -1.
            if self.current_index >= len(self.encoding):
                return -1

            quantity = self.encoding[self.current_index]
            value = self.encoding[self.current_index + 1]

            # Enough elements in current run
            if quantity >= remaining_elements:
                self.encoding[self.current_index] -= remaining_elements
                return value

            # Not enough elements in the current run; use them all
            else:
                remaining_elements -= quantity
                self.current_index += 2

        return -1

Big(O) Analysis

Time Complexity

O(k) – The time complexity is determined by how many number-character pairs we iterate through in the input array, where k is the number of these pairs. In the next() method, we loop through the compressed sequence only until we either fulfill the requested quantity or exhaust the sequence. Therefore, in the worst-case scenario, we might iterate through all number-character pairs in the input array once. This means the overall time complexity is O(k), where k is the number of number-character pairs.

Space Complexity

O(1) – The RLE iterator uses a constant amount of extra space. It only requires a few integer variables to keep track of the current index within the compressed array and the remaining count for the current number-character pair. No additional data structures are created that scale with the input size N, where N represents the length of the input array. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty input array	If the input array is empty, return -1 as no values exist.
Array with only one element	If the array has only one element, and next(n) is called it should return -1 since no (count,value) pair exists after consuming all the previous values.
next(n) called with n=0	When n is zero, no values should be consumed, and the function should return the current value without any changes to internal state.
n exceeds the count of the current element	Consume the full count of the current element and move to the next (count,value) pair, returning the current value if values remain or -1 if it is the last element.
Multiple calls to next(n) deplete the array	Ensure that after multiple calls to next(n), if all elements are exhausted, subsequent calls return -1.
Large counts that could lead to integer overflow when decrementing	Use appropriate data types (e.g., long) to handle large count values and prevent integer overflow during subtraction.
Alternating counts and values lead to many iterations	The solution should efficiently handle cases where next(n) is called with a small 'n' value when there are a large number of (count, value) pairs.
Input array contains zero counts	Treat zero counts as if the count is non-existent, skipping them and moving onto the next valid pair.

Empty input array

How to Handle:

If the input array is empty, return -1 as no values exist.

Array with only one element

How to Handle:

If the array has only one element, and next(n) is called it should return -1 since no (count,value) pair exists after consuming all the previous values.

next(n) called with n=0

How to Handle:

When n is zero, no values should be consumed, and the function should return the current value without any changes to internal state.

n exceeds the count of the current element

How to Handle:

Consume the full count of the current element and move to the next (count,value) pair, returning the current value if values remain or -1 if it is the last element.

Multiple calls to next(n) deplete the array

How to Handle:

Ensure that after multiple calls to next(n), if all elements are exhausted, subsequent calls return -1.

Large counts that could lead to integer overflow when decrementing

How to Handle:

Use appropriate data types (e.g., long) to handle large count values and prevent integer overflow during subtraction.

Alternating counts and values lead to many iterations

How to Handle:

The solution should efficiently handle cases where next(n) is called with a small 'n' value when there are a large number of (count, value) pairs.

Input array contains zero counts

How to Handle:

Treat zero counts as if the count is non-existent, skipping them and moving onto the next valid pair.