1
/*
2
    https://leetcode.com/problems/rle-iterator/
3

4
    next(): TC: O(n) in total over n calls
5
    Idea is to use two pointers are this.
6
    We maintain a ptr that points to the current element bucket. For a given n
7
    first iterate through the buckets which have freq < n, this means they won't
8
   have the last element. Once the iteration ends, either we will have no
9
   elements left or we will be on the bucket with freq >= n. Update the
10
   iteration ptr accordingly.
11
*/
12
class RLEIterator {
13
  vector<int> encoding;
14
  // Tracks the even indices
15
  int curr = -1;
16
  // Tracks the total length of array
17
  int len = 0;
18

19
 public:
20
  RLEIterator(vector<int> &encoding) {
21
    this->encoding = encoding;
22
    curr = 0;
23
    len = encoding.size();
24
  }
25

26
  int next(int n) {
27
    // Skip all the number buckets which will be completely exhausted
28
    // and we will still have some n left i.e n > 0
29
    for (; curr < len && n > 0 && encoding[curr] < n; curr += 2) {
30
      // Skip the buckets with 0 frequency
31
      if (encoding[curr] == 0) continue;
32
      n -= encoding[curr];
33
    }
34

35
    int element = -1;
36
    //  If we still have elements left with non zero frequency then
37
    // the current bucket's frequency will be >= leftover n
38
    if (curr < len && encoding[curr] >= n) {
39
      // Exhaust the leftover n
40
      encoding[curr] -= n;
41
      element = encoding[curr + 1];
42
      // If the bucket is completely exhausted, then move the iterator ptr to
43
      // next element for the next function call
44
      if (encoding[curr] == 0) curr += 2;
45
    }
46
    return element;
47
  }
48
};
49

50
/**
51
 * Your RLEIterator object will be instantiated and called as such:
52
 * RLEIterator* obj = new RLEIterator(encoding);
53
 * int param_1 = obj->next(n);
54
 */