Skip to content

900. RLE Iterator

  • Time: Constructor: $O(|\texttt{encoding}|)$, next(n: int): $O(1)$
  • Space: $O(|\texttt{encoding}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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]