Algorithm

Problem Name: 900. RLE Iterator

Problem Link: https://leetcode.com/problems/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]], [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 to next.

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

x
–
+
cmd
["RLEIterator", "next", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]

Output

x
–
+
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 & Try With Live Editor

Input

x
–
+
cmd
["RLEIterator", "next", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]

Output

x
–
+
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 & Try With Live Editor

Input

x
–
+
cmd
["RLEIterator", "next", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]

Output

x
–
+
cmd
[null, 8, 8, 5, -1]
Advertisements

Demonstration

Previous
#899 Leetcode Orderly Queue Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#901 Leetcode Online Stock Span Solution in C, C++, Java, JavaScript, Python, C# Leetcode