## Algorithm

Problem Name: 900. RLE Iterator

We can use run-length encoding (i.e., RLE) to encode a sequence of integers. In a run-length encoded array of even length `encoding` (0-indexed), for all even `i`, `encoding[i]` tells us the number of times that the non-negative integer value `encoding[i + 1]` is repeated in the sequence.

• For example, the sequence `arr = [8,8,8,5,5]` can be encoded to be `encoding = [3,8,2,5]`. `encoding = [3,8,0,9,2,5]` and `encoding = [2,8,1,8,2,5]` are also valid RLE of `arr`.

Given a run-length encoded array, design an iterator that iterates through it.

Implement the `RLEIterator` class:

• `RLEIterator(int[] encoded)` Initializes the object with the encoded array `encoded`.
• `int next(int n)` Exhausts the next `n` elements and returns the last element exhausted in this way. If there is no element left to exhaust, return `-1` instead.

Example 1:

```Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], , , , ]
Output
[null, 8, 8, 5, -1]

Explanation
RLEIterator rLEIterator = new RLEIterator([3, 8, 0, 9, 2, 5]); // This maps to the sequence [8,8,8,5,5].
rLEIterator.next(2); // exhausts 2 terms of the sequence, returning 8. The remaining sequence is now [8, 5, 5].
rLEIterator.next(1); // exhausts 1 term of the sequence, returning 8. The remaining sequence is now [5, 5].
rLEIterator.next(1); // exhausts 1 term of the sequence, returning 5. The remaining sequence is now .
rLEIterator.next(2); // exhausts 2 terms, returning -1. This is because the first term exhausted was 5,
but the second term did not exist. Since the last term exhausted does not exist, we return -1.
```

Constraints:

• `2 <= encoding.length <= 1000`
• `encoding.length` is even.
• `0 <= encoding[i] <= 109`
• `1 <= n <= 109`
• At most `1000` calls will be made to `next`.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
lass RLEIterator {
public:
RLEIterator(vector A) {
for (auto x: A) {
nums.push_back(x);
}
}

int next(int n) {
while (!nums.empty() && nums.front() < n ) {
n -= nums.front();
nums.pop_front();
nums.pop_front();
}
if (nums.empty()) {
return -1;
}
int count = nums.front();
nums.pop_front();
int res = nums.front();
count -= n;
if (count == 0) {a
nums.pop_front();
} else {
nums.push_front(count);
}
return res;
}

private:
dequenums;
};
``````
Copy The Code &

Input

cmd
["RLEIterator", "next", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], , , , ]

Output

cmd
[null, 8, 8, 5, -1]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class RLEIterator {

int[] encoding;
int currCounterIdx;

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

public int next(int n) {
while (n > 0) {
while (this.encoding[this.currCounterIdx] == 0 && this.currCounterIdx + 2 < this.encoding.length) {
this.currCounterIdx += 2;
}
if (this.encoding[this.currCounterIdx] == 0) {
return -1;
}
int diff = Math.min(this.encoding[this.currCounterIdx], n);
this.encoding[this.currCounterIdx] -= diff;
n -= diff;
}
return this.encoding[this.currCounterIdx + 1];
}
}
``````
Copy The Code &

Input

cmd
["RLEIterator", "next", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], , , , ]

Output

cmd
[null, 8, 8, 5, -1]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class RLEIterator:

def __init__(self, A):
self.it = A[::-1]

def next(self, n):
while self.it and self.it[-1] <= n:
if self.it[-1]: last = self.it[-2]
n -= self.it.pop()
self.it.pop()
if n and self.it:
self.it[-1] -= n
last = self.it[-2]
return last if self.it else -1

``````
Copy The Code &

Input

cmd
["RLEIterator", "next", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], , , , ]

Output

cmd
[null, 8, 8, 5, -1]