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 beencoding = [3,8,2,5]
.encoding = [3,8,0,9,2,5]
andencoding = [2,8,1,8,2,5]
are also valid RLE ofarr
.
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 arrayencoded
.int next(int n)
Exhausts the nextn
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]], [2], [1], [1], [2]] 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 [5]. 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 tonext
.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
lass RLEIterator {
public:
RLEIterator(vector<int> 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:
deque < int>nums;
};
Copy The Code &
Try With Live Editor
Input
Output
#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 &
Try With Live Editor
Input
Output
#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 &
Try With Live Editor
Input
Output