We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

RLE Iterator

Difficulty: Medium

Problem Description

Implement an iterator for a run-length encoded array that allows you to exhaust a specified number of elements and return the last element exhausted. If there are no elements left, return -1.

Key Insights

  • The run-length encoding consists of pairs of counts and values.
  • You need to keep track of the current position in the encoded array.
  • When calling the next function, you need to check if there are enough elements left to exhaust.
  • If the required number of elements to exhaust exceeds the available count, return -1.

Space and Time Complexity

Time Complexity: O(1) for each call to next, as it processes a fixed number of operations regardless of input size.
Space Complexity: O(1) since we are using a fixed amount of extra space.

Solution

The solution involves using a class RLEIterator to manage the state of the iterator and the current position in the encoded array. The class will have:

  1. A constructor to initialize the encoded array and set the current index and available count.
  2. A next method that takes an integer n and exhausts n elements, updating the current index and count accordingly.

The algorithm iterates through the encoded array, decrementing the count of the current value until the required elements are exhausted or the array is fully processed.

Code Solutions

class RLEIterator:
    def __init__(self, encoding):
        self.encoding = encoding
        self.index = 0
        self.count = 0

    def next(self, n):
        while n > 0:
            if self.count == 0:  # If count is 0, move to the next pair
                if self.index >= len(self.encoding):  # Check if we are out of bounds
                    return -1
                self.count = self.encoding[self.index]  # Set count from encoding
                self.value = self.encoding[self.index + 1]  # Set current value
                self.index += 2  # Move to the next pair

            if n <= self.count:  # If we can satisfy the request
                self.count -= n  # Decrease the available count
                return self.value  # Return the current value
            n -= self.count  # Otherwise, reduce the required count
            self.count = 0  # Set count to 0 to process next pair
        return -1  # If we exhaust all elements and still need more
← Back to All Questions