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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

RLE Iterator

Number: 936

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Design an iterator for a run-length encoded array. The iterator is initialized with an encoded array where for every even index i, the value at encoding[i] represents the count of the integer given at encoding[i+1]. The iterator has a method next(n) that exhausts the next n elements in the sequence. It returns the last element that was exhausted if possible, or -1 if there aren’t enough elements.

Key Insights

  • Maintain an index pointer into the encoded array to avoid decompressing the entire array.
  • In each call to next(n), decrement the count at the current pointer.
  • If the current count is not enough to cover n, subtract the count from n and move to the next pair.
  • Return the corresponding integer when the current count is sufficient; if the pointer goes out of range, return -1.

Space and Time Complexity

Time Complexity: O(1) on average per next call, though in worst-case each call may iterate over multiple encoding pairs (O(m) where m is number of encoding pairs, but m <= 500 given constraints). Space Complexity: O(1) as only a few extra variables are used.

Solution

We implement the RLEIterator by storing the encoded sequence and a pointer which tracks the current position. For each call to next(n), we subtract from the current count until either we have used up n or exhausted all pairs. If the count at the current position is sufficient, we return the corresponding integer after deducting n from the count. Otherwise, we decrement n by the current count and advance the pointer to the next encoding pair. The trick is to work directly with the encoding array without fully expanding it into its original sequence.

Code Solutions

# Define the RLEIterator class
class RLEIterator:
    # Initialize with the encoded array and a pointer for position
    def __init__(self, encoding):
        # Store the encoded list and initialize pointer to start (0 index)
        self.encoding = encoding
        self.index = 0

    # The next method consumes n elements and returns the value of the last element exhausted
    def next(self, n):
        # Loop until we find a block that can cover n or we run out of encoded blocks
        while self.index < len(self.encoding):
            # If current block's count is enough for n
            if self.encoding[self.index] >= n:
                # Deduct n from the block count
                self.encoding[self.index] -= n
                # Return the corresponding value
                return self.encoding[self.index + 1]
            # If not enough, subtract the current block's count from n
            n -= self.encoding[self.index]
            # Move to next pair (skip both count and value)
            self.index += 2
        # If no elements left to consume, return -1
        return -1
← Back to All Questions