Java O(n) Time and O(1) Space Approach without Modifying the Input Array
IntuitionImplement an iterator that uses constant space, and does not modify the original array.Algorithm
Maintain an extra variable repetitionsRemaining to kee
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Implement an iterator that uses constant space, and does not modify the original array.

# Algorithm
<!-- Describe your approach to solving the problem. -->
1. Maintain an extra variable *repetitionsRemaining* to keep track of how many of each current number are available to exhaust. That way, updates on the number counts can be performed on that variable instead of the original array.
2. Exhaust numbers until we reach an element that has enough numbers to exhaust for the remaining n. That will be the element that is to be returned in the next step. If we reach the end of the array before this is fulfilled, then there are not enough numbers, in which case return -1.
3. Exhaust any remaining n numbers from that element from the previous step, then return that element.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n)$$ In the worst-case scenario, the entire array will need to be traversed to exhaust n elements.

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(1)$$ Regardless of input array length or n, this implementation will always use three variables.

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

    public RLEIterator(int[] encoding) {
        this.encoding = encoding;
        index = 0;
        repetitionsRemaining = (encoding.length >= 2) ? encoding[0] : 0;
    }
    
    // This implementation does not produce any side effects
    public int next(int n) {
        if (n <= 0 || index + 1 >= encoding.length) {
            return -1;
        }

        while (repetitionsRemaining < n) {
            n -= repetitionsRemaining;
            index += 2;

            // End of array check
            if (index + 1 >= encoding.length) {
                return -1;
            }

            repetitionsRemaining = encoding[index];
        }

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

/**
 * Your RLEIterator object will be instantiated and called as such:
 * RLEIterator obj = new RLEIterator(encoding);
 * int param_1 = obj.next(n);
 */
```
['Array', 'Design', 'Counting', 'Iterator', 'Java']