900. RLE Iterator LeetCode Solution

In this guide, you will get 900. RLE Iterator LeetCode Solution with the best time and space complexity. The solution to RLE Iterator problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
RLE Iterator solution in C++
RLE Iterator solution in Java
RLE Iterator solution in Python
Additional Resources

900. RLE Iterator LeetCode Solution image

Problem Statement of 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.

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(|\texttt{encoding}|)

900. RLE Iterator LeetCode Solution in C++

class RLEIterator {
 public:
  RLEIterator(vector<int>& encoding) : encoding(encoding) {}

  int next(int n) {
    while (index < encoding.size() && encoding[index] < n) {
      n -= encoding[index];
      index += 2;
    }

    if (index == encoding.size())
      return -1;

    encoding[index] -= n;
    return encoding[index + 1];
  }

 private:
  int index = 0;
  vector<int> encoding;
};
/* code provided by PROGIEZ */

900. RLE Iterator LeetCode Solution in Java

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

  public int next(int n) {
    while (index < encoding.length && encoding[index] < n) {
      n -= encoding[index];
      index += 2;
    }

    if (index == encoding.length)
      return -1;

    encoding[index] -= n;
    return encoding[index + 1];
  }

  private int index = 0;
  private int[] encoding;
}
// code provided by PROGIEZ

900. RLE Iterator LeetCode Solution in Python

class RLEIterator:
  def __init__(self, encoding: list[int]):
    self.encoding = encoding
    self.index = 0

  def next(self, n: int) -> int:
    while self.index < len(self.encoding) and self.encoding[self.index] < n:
      n -= self.encoding[self.index]
      self.index += 2

    if self.index == len(self.encoding):
      return -1

    self.encoding[self.index] -= n
    return self.encoding[self.index + 1]
 # code by PROGIEZ