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.

Input Format

Java

class RLEIterator {

    public RLEIterator(int[] encoding) {
        
    }
    
    public int next(int n) {
        
    }
}

Solution

Method 1 - Iterator with Pointer and Consumption

Intuition

We maintain a pointer to the current run in the encoding and a counter for how many elements remain in that run. For each next(n) call, we consume elements from the current run, moving to the next run as needed, and return the last value exhausted, or -1 if we run out.

Approach

Store the encoding array and a pointer to the current run (index).
For each next(n) call:
- While n > 0 and there are runs left:
  - If the current run has enough elements, consume n and return the value.
  - Otherwise, consume all remaining elements in the current run, subtract from n, and move to the next run.
If we run out of runs before exhausting n, return -1.

Code

[{"language":"C++","code":"class RLEIterator {\n    vector<int> encoding;\n    int idx = 0;\npublic:\n    RLEIterator(vector<int>& A) : encoding(A) {}\n    int next(int n) {\n        while (idx < encoding.size() && n > 0) {\n            if (encoding[idx] >= n) {\n                encoding[idx] -= n;\n                return encoding[idx + 1];\n            } else {\n                n -= encoding[idx];\n                encoding[idx] = 0;\n                idx += 2;\n            }\n        }\n        return -1;\n    }\n};","lang":"cpp"},{"language":"Go","code":"type RLEIterator struct {\n    encoding []int\n    idx      int\n}\n\nfunc Constructor(encoding []int) RLEIterator {\n    return RLEIterator{encoding, 0}\n}\n\nfunc (it *RLEIterator) Next(n int) int {\n    for it.idx < len(it.encoding) && n > 0 {\n        if it.encoding[it.idx] >= n {\n            it.encoding[it.idx] -= n\n            return it.encoding[it.idx+1]\n        }\n        n -= it.encoding[it.idx]\n        it.idx += 2\n    }\n    return -1\n}","lang":"go"},{"language":"Java","code":"class RLEIterator {\n    private int[] encoding;\n    private int idx = 0;\n\n    public RLEIterator(int[] encoding) {\n        this.encoding = encoding;\n    }\n\n    public int next(int n) {\n        while (idx < encoding.length && n > 0) {\n            if (encoding[idx] >= n) {\n                encoding[idx] -= n;\n                return encoding[idx + 1];\n            } else {\n                n -= encoding[idx];\n                idx += 2;\n            }\n        }\n        return -1;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class RLEIterator(private val encoding: IntArray) {\n    private var idx = 0\n\n    fun next(n: Int): Int {\n        var nLeft = n\n        while (idx < encoding.size && nLeft > 0) {\n            if (encoding[idx] >= nLeft) {\n                encoding[idx] -= nLeft\n                return encoding[idx + 1]\n            } else {\n                nLeft -

Related Tags