##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/900.html

# 900. RLE Iterator (Medium)

Write an iterator that iterates through a run-length encoded sequence.

The iterator is initialized by RLEIterator(int[] A), where A is a run-length encoding of some sequence.  More specifically, for all even iA[i] tells us the number of times that the non-negative integer value A[i+1] is repeated in the sequence.

The iterator supports one function: next(int n), which exhausts the next n elements (n >= 1) and returns the last element exhausted in this way.  If there is no element left to exhaust, next returns -1 instead.

For example, we start with A = [3,8,0,9,2,5], which is a run-length encoding of the sequence [8,8,8,5,5].  This is because the sequence can be read as "three eights, zero nines, two fives".

Example 1:

Input: ["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],,,,]
Output: [null,8,8,5,-1]
Explanation:
RLEIterator is initialized with RLEIterator([3,8,0,9,2,5]).
This maps to the sequence [8,8,8,5,5].
RLEIterator.next is then called 4 times:

.next(2) exhausts 2 terms of the sequence, returning 8.  The remaining sequence is now [8, 5, 5].

.next(1) exhausts 1 term of the sequence, returning 8.  The remaining sequence is now [5, 5].

.next(1) exhausts 1 term of the sequence, returning 5.  The remaining sequence is now .

.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.



Note:

1. 0 <= A.length <= 1000
2. A.length is an even integer.
3. 0 <= A[i] <= 10^9
4. There are at most 1000 calls to RLEIterator.next(int n) per test case.
5. Each call to RLEIterator.next(int n) will have 1 <= n <= 10^9.

Related Topics:
Array

## Solution 1.

• class RLEIterator {
private int[] encoding;
private int curr;
private int i;

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

public int next(int n) {
while (i < encoding.length) {
if (curr + n > encoding[i]) {
n -= encoding[i] - curr;
i += 2;
curr = 0;
} else {
curr += n;
return encoding[i + 1];
}
}
return -1;
}
}

/**
* Your RLEIterator object will be instantiated and called as such:
* RLEIterator obj = new RLEIterator(encoding);
* int param_1 = obj.next(n);
*/

• class RLEIterator {
public:
vector<int> encoding;
int curr;
int i;

RLEIterator(vector<int>& encoding) {
this->encoding = encoding;
this->curr = 0;
this->i = 0;
}

int next(int n) {
while (i < encoding.size()) {
if (curr + n > encoding[i]) {
n -= encoding[i] - curr;
curr = 0;
i += 2;
} else {
curr += n;
return encoding[i + 1];
}
}
return -1;
}
};

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

• class RLEIterator:
def __init__(self, encoding: List[int]):
self.encoding = encoding
self.i = 0
self.curr = 0

def next(self, n: int) -> int:
while self.i < len(self.encoding):
if self.curr + n > self.encoding[self.i]:
n -= self.encoding[self.i] - self.curr
self.curr = 0
self.i += 2
else:
self.curr += n
return self.encoding[self.i + 1]
return -1

# Your RLEIterator object will be instantiated and called as such:
# obj = RLEIterator(encoding)
# param_1 = obj.next(n)


• type RLEIterator struct {
encoding []int
curr     int
i        int
}

func Constructor(encoding []int) RLEIterator {
return RLEIterator{encoding: encoding, curr: 0, i: 0}
}

func (this *RLEIterator) Next(n int) int {
for this.i < len(this.encoding) {
if this.curr+n > this.encoding[this.i] {
n -= this.encoding[this.i] - this.curr
this.curr = 0
this.i += 2
} else {
this.curr += n
return this.encoding[this.i+1]
}
}
return -1
}

/**
* Your RLEIterator object will be instantiated and called as such:
* obj := Constructor(encoding);
* param_1 := obj.Next(n);
*/