algoadvance

(From LeetCode #900 “RLE Iterator”)

Write an iterator that iterates through a run-length encoded sequence.

The iterator is initialized by RLEIterator(int[] A), where A is a run-length encoded array of even length. Specifically, for all even indices i, A[i] tells us the number of times that the non-negative integer value A[i + 1] is repeated in the sequence.

The iterator supports one function: next(int n), which exhausts the next n elements (n >= 1) and returns the last element exhausted in this way. If there is no element left to exhaust, next returns -1 instead.

In other words, next(n)`` returns the last element of the next n elements. Note that n is guaranteed to be a positive integer.

Example:

Input: ["RLEIterator","next","next","next","next"], 
       [[[3,8,0,9,2,5]], [2], [1], [1], [2]]
Output: [null,8,8,5,-1]
Explanation:
RLEIterator rle = new RLEIterator([3,8,0,9,2,5]);
rle.next(2); // exhausts 2 terms of the sequence, returns 8.
rle.next(1); // exhausts the next 1 term of the sequence, returns 8.
rle.next(1); // exhausts the next 1 term of the sequence, returns 5.
rle.next(2); // pass returns -1 because there are only 1 term left in the sequence.

Clarifying Questions

1. What constraints are placed on the size of the array A and the values it contains?

   • The length of A is guaranteed to be even, representing pairs of [frequency, value].
   • Frequency values (A[i]) and the integers (A[i + 1]) are non-negative.

2. Can the frequency of elements be zero?

   • Yes, frequencies can be zero, which means those elements do not appear in the sequence.

Strategy

1. Initialization (__init__ method)
   • Initialize by storing the input array A and setting an index pointer to track the current position in A.
2. Next method (next method)
   • Process elements from A based on the frequency.
   • Decrement the frequency while advancing the iterator.
   • If the frequency for a given value is exhausted, move to the next value.
   • Return the last value reached or -1 if there are not enough elements left in the sequence.

Code

class RLEIterator:
    
    def __init__(self, A):
        self.data = A
        self.index = 0   # This will keep track of the current position in the encoded array
    
    def next(self, n):
        while self.index < len(self.data):
            if self.data[self.index] >= n:  # sufficient elements in the current run
                self.data[self.index] -= n
                return self.data[self.index + 1]
            else:
                n -= self.data[self.index]  # exhaust all elements in the current run
                self.index += 2  # move to the next pair
        
        return -1

# Example usage:
rle = RLEIterator([3,8,0,9,2,5])
print(rle.next(2))  # returns 8
print(rle.next(1))  # returns 8
print(rle.next(1))  # returns 5
print(rle.next(2))  # returns -1

Time Complexity

• Initialization (__init__): O(1) – Simply setting up the initial state, which takes constant time.

• Next method (next): O(n) – In the worst-case, we might need to scan through each element in the array if n is large and there are many runs with zero or small counts. Here n refers to the number of elements to pick, not the size of the input array.

The approach ensures that each call to next efficiently manages the run-length encoded sequence by leveraging the inherent structure of the data (frequency-value pairs).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?