# RLE Iterator
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rle-iterator)
Canonical: https://scaleengineer.com/dsa/problems/rle-iterator
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Iterator](https://scaleengineer.com/dsa/patterns/iterator)
**Data structures:** Array
---
## Problem
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`.

# Approaches
## Approach 1: Decompression to a Full Sequence
This brute-force approach involves pre-processing the run-length encoded array by fully decompressing it into the actual sequence of numbers. The constructor builds a large list containing every number in the sequence. The `next` method then simply advances a pointer through this pre-built list to find the required element.
**Time:** O(S) for the constructor, where S is the total number of elements in the decompressed sequence. Each `next(n)` call is O(1). The high cost of the constructor makes this approach inefficient. · **Space:** O(S), where S is the total number of elements in the decompressed sequence (i.e., the sum of all counts in the `encoding` array). This can be extremely large.
**Pros:** The logic is straightforward and easy to understand.; Once the initial decompression is done, each `next(n)` call is very fast, operating in constant time.
**Cons:** The constructor's time complexity is proportional to the total number of elements in the sequence (`S`), which can be enormous (`1000 * 10^9`), leading to a Time Limit Exceeded (TLE) error.; The space complexity is also `O(S)`, which will almost certainly cause a Memory Limit Exceeded (MLE) error given the constraints.; This approach is not feasible for the problem's constraints.
### Explanation
The `RLEIterator` class maintains the entire expanded sequence in a list (e.g., `ArrayList` in Java) and a pointer or index to the current position in this sequence.

**Constructor (`RLEIterator(int[] encoding)`):**
- It initializes an empty list.
- It then iterates through the input `encoding` array, taking elements two at a time. For each pair `(count, value)`, it adds the `value` to the list `count` times.
- This process fully expands the run-length encoded data into a standard sequence, which is stored for later use.
- An index, say `cursor`, is initialized to 0.

**`next(int n)` Method:**
- This method simulates moving `n` steps forward in the decompressed list.
- It checks if moving `n` steps from the current `cursor` position will go past the end of the list (`cursor + n > list.size()`).
- If it does, it means we cannot exhaust `n` elements. The iterator exhausts all remaining elements, and as per the problem, returns `-1`.
- Otherwise, it advances the `cursor` by `n` and returns the element at the new position minus one (`list.get(cursor - 1)`), which is the last element exhausted.

```java
import java.util.ArrayList;
import java.util.List;

class RLEIterator {
    private List<Long> decompressed;
    private int index;

    public RLEIterator(int[] encoding) {
        // Note: Using Long for counts to avoid overflow, though List size is limited by Integer.MAX_VALUE
        // This approach is fundamentally flawed by memory limits regardless.
        this.decompressed = new ArrayList<>();
        this.index = 0;
        for (int i = 0; i < encoding.length; i += 2) {
            long count = encoding[i];
            int value = encoding[i + 1];
            for (long j = 0; j < count; j++) {
                // This loop is the source of the TLE/MLE
                this.decompressed.add((long)value);
            }
        }
    }

    public int next(int n) {
        if (this.index + n > this.decompressed.size()) {
            this.index = this.decompressed.size(); // Exhaust all remaining
            return -1;
        }
        this.index += n;
        return this.decompressed.get(this.index - 1).intValue();
    }
}
```
### Algorithm
- **Initialization:** In the constructor, create a new list to hold the decompressed sequence and an index to track the current position.
- **Decompression:** Iterate through the `encoding` array. For each pair `(count, value)`, add `value` to the list `count` times. This happens once during initialization.
- **`next(n)` Call:**
  - Calculate the target position by adding `n` to the current index.
  - Check if the target position is beyond the bounds of the decompressed list.
  - If it is, there are not enough elements. Update the index to the end of the list and return `-1`.
  - If there are enough elements, update the index to the target position and return the element at `index - 1`.

## Approach 2: In-place Pointer Iteration
This optimal approach avoids the massive memory and time costs of decompression by working with the `encoding` array directly. It uses a pointer to keep track of the current position in the encoded data. When `next(n)` is called, it iterates through the encoded pairs, consuming elements on-the-fly until `n` elements have been exhausted.
**Time:** O(N) for all calls to `next` combined, where N is the length of the `encoding` array. The `index` pointer only moves forward, so it will traverse the array at most once across all calls. The constructor is O(1). · **Space:** O(1) extra space, as it only stores a pointer. It modifies the input array in-place.
**Pros:** Extremely efficient in terms of space, using only O(1) extra space.; Efficient in time. The total work done across all `next` calls is proportional to the length of the `encoding` array, not the size of the decompressed sequence.; It's the optimal solution for the given constraints.
**Cons:** This approach modifies the input `encoding` array. If the original array must be preserved, a copy should be made in the constructor, which would increase the space complexity to O(N), where N is the length of the `encoding` array.
### Explanation
Instead of creating a new, potentially huge, data structure, this method cleverly uses the input `encoding` array itself to maintain the state of the iterator. It only needs one extra piece of information: an index or pointer to the current group `(count, value)` it is processing.

**State:**
- `int[] encoding`: The run-length encoded array.
- `int index`: A pointer to the start of the current group in the `encoding` array (always an even number).

**Constructor (`RLEIterator(int[] encoding)`):**
- It simply stores a reference to the `encoding` array and initializes the `index` pointer to 0. This is a very fast O(1) operation.

**`next(int n)` Method:**
- The method enters a loop that continues as long as there are groups left to process (`index < encoding.length`).
- Inside the loop, it looks at the current group's count, `encoding[index]`.
- If `n` is smaller than or equal to the current count, it means the group has enough elements to satisfy the request. The last element exhausted will be the value of this group, `encoding[index + 1]`. We subtract `n` from the count (`encoding[index] -= n`) to reflect the consumption and return the value.
- If `n` is larger than the current count, the entire group is consumed. We subtract the count from `n` (`n -= encoding[index]`) and advance our `index` by 2 to move to the next group.
- If the loop completes, it means we have traversed all the groups but still couldn't exhaust `n` elements. In this case, we return `-1`.

```java
class RLEIterator {
    private int[] encoding;
    private int index;

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

    public int next(int n) {
        while (index < encoding.length) {
            // If the current group has enough elements to satisfy the request
            if (n <= encoding[index]) {
                encoding[index] -= n;
                return encoding[index + 1];
            }
            
            // Otherwise, the current group is not enough.
            // Exhaust the current group and move to the next.
            n -= encoding[index];
            index += 2;
        }
        
        // If the loop finishes, we've run out of elements in the sequence.
        return -1;
    }
}
```
### Algorithm
- **Initialization:** Store the `encoding` array and an index pointer, `ptr`, initialized to 0.
- **`next(n)` Call:**
  - Loop as long as the pointer `ptr` is within the bounds of the `encoding` array.
  - Let `count` be `encoding[ptr]` and `value` be `encoding[ptr + 1]`.
  - **Case 1: `n <= count`** (The current group has enough elements).
    - Decrease the group's count by `n`: `encoding[ptr] -= n`.
    - The last element exhausted is `value`, so return it.
  - **Case 2: `n > count`** (The current group is not enough).
    - Exhaust the entire current group. Decrease `n` by `count`: `n -= encoding[ptr]`.
    - Move the pointer to the next group: `ptr += 2`.
- **Termination:** If the loop finishes (i.e., `ptr` goes out of bounds) without returning a value, it means there were not enough elements in the entire sequence to satisfy the `next(n)` call. Return `-1`.

# Solutions
### Java

```java
class RLEIterator { private int [] encoding ; private int i ; private int j ; public RLEIterator ( int [] encoding ) { this . encoding = encoding ; } public int next ( int n ) { while ( i < encoding . length ) { if ( encoding [ i ] - j < n ) { n -= ( encoding [ i ] - j ); i += 2 ; j = 0 ; } else { j += 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); */
```

### CPP

```cpp
class RLEIterator { public: RLEIterator ( vector < int >& encoding ) { this -> encoding = encoding ; } int next ( int n ) { while ( i < encoding . size ()) { if ( encoding [ i ] - j < n ) { n -= ( encoding [ i ] - j ); i += 2 ; j = 0 ; } else { j += n ; return encoding [ i + 1 ]; } } return - 1 ; } private: vector < int > encoding ; int i = 0 ; int j = 0 ; }; /** * Your RLEIterator object will be instantiated and called as such: * RLEIterator* obj = new RLEIterator(encoding); * int param_1 = obj->next(n); */
```

### Python

```python
class RLEIterator : def __init__ ( self , encoding : List [ int ]): self . encoding = encoding self . i = 0 self . j = 0 def next ( self , n : int ) -> int : while self . i < len ( self . encoding ): if self . encoding [ self . i ] - self . j < n : n -= self . encoding [ self . i ] - self . j self . i += 2 self . j = 0 else : self . j += 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)
```