algoadvance

Leetcode 900. RLE Iterator

Problem Statement

Design 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. Specifically, for an integer sequence S, each element in the array A is described by a pair of elements: the first element is the count of the number of times the second element occurs in the uncompressed sequence. For example, the sequence S = [100, 200, 300, 300, 300] can be encoded to A = [1, 100, 1, 200, 3, 300].

The iterator supports the function next(int n), where it exhausts the next n elements in the sequence and returns the last element exhausted. If there are no more elements to exhaust, (n) must return -1 instead.

Clarifying Questions

1. Can the input array A be empty?
   • (Assume no, the input array A will always represent a valid encoded sequence.)
2. Can the next function be called with n greater than the remaining elements?
   • (Yes, if n exceeds the remaining elements, the function should return -1.)

Strategy

1. Data Structure Design:
   • We’ll maintain the array A and an index to keep track of our current position within this run-length encoded array.
   • We will keep a count of the elements processed to efficiently navigate through the array.
2. next Function:
   • For each call to next(n), we will decrement n by the count of the current element until n is 0 or there are no more elements to process.
   • If we exhaust all elements and n is still greater than 0, we’ll return -1.

Time Complexity

• Initialization: O(1)
• Each call to next(n): O(m) in the worst case, where m is the number of pairs in the A array, but typically better since we skip large chunks based on the counts directly.

Code

#include <vector>

class RLEIterator {
public:
    RLEIterator(std::vector<int>& A) : encodedArray(A), index(0), remaining(0) {}

    int next(int n) {
        while (index < encodedArray.size()) {
            if (remaining == 0) {  // no remaining counts, move to next pair
                remaining = encodedArray[index];
                current = encodedArray[index + 1];
            }
            
            if (remaining >= n) {  // we can fulfill the request with the current element
                remaining -= n;
                return current;
            } else {  // we cannot fulfill the request, move to next pair
                n -= remaining;
                index += 2;
                remaining = 0;
            }
        }
        
        return -1;  // exhausted all elements
    }

private:
    std::vector<int> encodedArray;
    int index;
    int current;
    int remaining;
};

// Example usage:
// std::vector<int> A = {3, 8, 0, 9, 2, 5};
// RLEIterator iterator(A);
// iterator.next(2); // returns 8
// iterator.next(1); // returns 8
// iterator.next(1); // returns 5
// iterator.next(2); // returns -1

Explanation:

• Constructor: Initializes the iterator with the encoded array A.
• next Function: Processes n elements based on the remaining count, decrements n accordingly, and keeps track of the current position in the encoded array. If we run out of elements, it returns -1.

This design ensures we efficiently iterate through the RLE encoded array, maintaining a balance between simplicity and performance.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?