900. RLE Iterator

• Time:
  • Constructor: $O(|\texttt{encoding}|)$
  • next(n: int): $O(1)$
• Space: $O(|\texttt{encoding}|)$

C++JavaPython

class RLEIterator {
 public:
  RLEIterator(vector<int>& encoding) : encoding(encoding) {}

  int next(int n) {
    while (index < encoding.size() && encoding[index] < n) {
      n -= encoding[index];
      index += 2;
    }

    if (index == encoding.size())
      return -1;

    encoding[index] -= n;
    return encoding[index + 1];
  }

 private:
  int index = 0;
  vector<int> encoding;
};

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

  public int next(int n) {
    while (index < encoding.length && encoding[index] < n) {
      n -= encoding[index];
      index += 2;
    }

    if (index == encoding.length)
      return -1;

    encoding[index] -= n;
    return encoding[index + 1];
  }

  private int index = 0;
  private int[] encoding;
}

class RLEIterator:
  def __init__(self, encoding: list[int]):
    self.encoding = encoding
    self.index = 0

  def next(self, n: int) -> int:
    while self.index < len(self.encoding) and self.encoding[self.index] < n:
      n -= self.encoding[self.index]
      self.index += 2

    if self.index == len(self.encoding):
      return -1

    self.encoding[self.index] -= n
    return self.encoding[self.index + 1]