RLE Iterator

medium design iterator run-length encoding

Problem

A run-length encoded sequence is given as an array encoding of even length, where pairs (count, value) mean the integer value repeated count times. Design an iterator whose next(n) exhausts the next n elements of the decoded sequence and returns the last element exhausted, or -1 if there are fewer than n elements left.

Inputencoding = [3, 8, 0, 9, 2, 5], calls = next(2), next(1), next(1), next(2)

Output[8, 8, 5, -1]

Decoded sequence is 8, 8, 8, 5, 5. next(2)→8, next(1)→8, next(1)→5, then next(2) needs 2 but only 1 remains → -1.

encoding (count, value pairs)

next(n) calls (comma-separated)

class RLEIterator:
    def __init__(self, encoding):
        self.enc = encoding
        self.i = 0          # index of current count

    def next(self, n):
        while self.i < len(self.enc):
            if n <= self.enc[self.i]:
                self.enc[self.i] -= n
                return self.enc[self.i + 1]
            n -= self.enc[self.i]
            self.i += 2
        return -1

class RLEIterator {
  constructor(encoding) {
    this.enc = encoding;
    this.i = 0;            // index of current count
  }
  next(n) {
    while (this.i < this.enc.length) {
      if (n <= this.enc[this.i]) {
        this.enc[this.i] -= n;
        return this.enc[this.i + 1];
      }
      n -= this.enc[this.i];
      this.i += 2;
    }
    return -1;
  }
}

class RLEIterator {
    private int[] enc;
    private int i = 0;          // index of current count

    public RLEIterator(int[] encoding) {
        this.enc = encoding;
    }

    public int next(int n) {
        while (i < enc.length) {
            if (n <= enc[i]) {
                enc[i] -= n;
                return enc[i + 1];
            }
            n -= enc[i];
            i += 2;
        }
        return -1;
    }
}

class RLEIterator {
    vector<int> enc;
    int i = 0;                  // index of current count
public:
    RLEIterator(vector<int>& encoding) : enc(encoding) {}

    int next(int n) {
        while (i < (int)enc.size()) {
            if (n <= enc[i]) {
                enc[i] -= n;
                return enc[i + 1];
            }
            n -= enc[i];
            i += 2;
        }
        return -1;
    }
};

Explanation

The sequence is stored compressed as (count, value) pairs, so we never actually build the full decoded list. Instead we keep a pointer i at the current count and shrink that count as we consume elements.

On each next(n) we look at the current block. If its remaining count is enough (n <= enc[i]), we subtract n from that count and return the block's value enc[i+1] — that is the last element we just exhausted.

If the block is too small, we use up all of it, lower n by that count, and jump to the next block with i += 2. We repeat until a block satisfies the request or we run off the end, in which case we return -1.

Because counts only ever shrink and the pointer only moves forward, the work spread across all calls is small — each block is visited just once.

Example: encoding = [3, 8, 0, 9, 2, 5] decodes to 8, 8, 8, 5, 5. next(2) takes two 8s (count becomes 1) and returns 8. Later next(2) needs two but only one 5 remains, so it returns -1.

Time: O(1) amortized per next Space: O(1)