900. RLE Iterator

DifficultyMedium

Description

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] <= 10⁹
1 <= n <= 10⁹
At most 1000 calls will be made to next.

Solutions

Solution 1: Maintain Two Pointers

Thinking

Run lengths reach \(10^9\), so expanding the encoding into a flat list is impossible, and consuming next one element at a time is equally infeasible when \(n\) is that large.

We therefore consume on the compressed form. The leftover in the current run is \(\textit{encoding}[i]-j\); if it is smaller than \(n\), skip the whole run and advance \(i\) by \(2\), otherwise only increment \(j\). Both pointers move forward, so all queries together scan the encoding once.

We define two pointers \(i\) and \(j\), where pointer \(i\) points to the current run-length encoding being read, and pointer \(j\) points to which character in the current run-length encoding is being read. Initially, \(i = 0\), \(j = 0\).

Each time we call next(n), we judge whether the remaining number of characters in the current run-length encoding \(encoding[i] - j\) is less than \(n\). If it is, we subtract \(n\) by \(encoding[i] - j\), add \(2\) to \(i\), and set \(j\) to \(0\), then continue to judge the next run-length encoding. If it is not, we add \(n\) to \(j\) and return \(encoding[i + 1]\).

If \(i\) exceeds the length of the run-length encoding and there is still no return value, it means that there are no remaining elements to be exhausted, and we return \(-1\).

The time complexity is \(O(n + q)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the run-length encoding, and \(q\) is the number of times next(n) is called.

Python3JavaC++GoTypeScript

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)

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);
 */

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);
 */

type RLEIterator struct {
    encoding []int
    i, j     int
}

func Constructor(encoding []int) RLEIterator {
    return RLEIterator{encoding, 0, 0}
}

func (this *RLEIterator) Next(n int) int {
    for this.i < len(this.encoding) {
        if this.encoding[this.i]-this.j < n {
            n -= (this.encoding[this.i] - this.j)
            this.i += 2
            this.j = 0
        } else {
            this.j += n
            return this.encoding[this.i+1]
        }
    }
    return -1
}

/**
 * Your RLEIterator object will be instantiated and called as such:
 * obj := Constructor(encoding);
 * param_1 := obj.Next(n);
 */

class RLEIterator {
    private encoding: number[];
    private i: number;
    private j: number;

    constructor(encoding: number[]) {
        this.encoding = encoding;
        this.i = 0;
        this.j = 0;
    }

    next(n: number): number {
        while (this.i < this.encoding.length) {
            if (this.encoding[this.i] - this.j < n) {
                n -= this.encoding[this.i] - this.j;
                this.i += 2;
                this.j = 0;
            } else {
                this.j += n;
                return this.encoding[this.i + 1];
            }
        }
        return -1;
    }
}

/**
 * Your RLEIterator object will be instantiated and called as such:
 * var obj = new RLEIterator(encoding)
 * var param_1 = obj.next(n)
 */

900. RLE Iterator

Description

Solutions

Solution 1: Maintain Two Pointers

Comments