algoadvance

Leetcode 900. RLE Iterator

Problem Statement

Let’s say you have a run-length encoded sequence, where each element in the array represents [count, value] pairs. For example, the sequence [3, 8, 0, 9, 2, 5] translates to 8, 8, 8, 5, 5.

Implement an iterator to decode the run-length encoded sequence:

• RLEIterator(int[] A): Initializes the object with an array A.
• int next(int n): Exhausts the next n elements and returns the last element exhausted in this way. If there is no element to be exhausted, return -1.

Example:

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]);
rLEIterator.next(2); // exhausts 2 terms and returns 8
rLEIterator.next(1); // exhausts 1 term and returns 8
rLEIterator.next(1); // exhausts 1 term and returns 5
rLEIterator.next(2); // exhausts 2 terms and returns -1

Clarifying Questions

1. Input Array Structure: Will the input array always be well-formed (even length, non-negative counts)?
   • Yes, the input array will always have non-negative counts and will have an even length.
2. Constraints on Array Size and Values:
   • The size of A and the maximum values of counts and elements will be within reasonable limits as typically expected in competitive programming.
3. Thread Safety: Is the class expected to be thread-safe?
   • No, thread safety is not a concern in this context.

Strategy

We can maintain a pointer or index to track the current [count, value] pair from the input array. The main operations will be:

1. Reducing the count as we call next(int n).
2. Moving to the next [count, value] pair when the current count is exhausted.
3. Returning the correct value or -1 when elements are exhausted.

Code

public class RLEIterator {
    private int[] encoding;
    private int index;
    private int remainingCount;

    public RLEIterator(int[] A) {
        this.encoding = A;
        this.index = 0;
        this.remainingCount = this.encoding.length == 0 ? 0 : this.encoding[0];
    }

    public int next(int n) {
        while (n > 0 && this.index < this.encoding.length) {
            if (n > this.remainingCount) {
                n -= this.remainingCount;
                this.index += 2;
                if (this.index < this.encoding.length) {
                    this.remainingCount = this.encoding[this.index];
                } else {
                    return -1;
                }
            } else {
                this.remainingCount -= n;
                return this.encoding[this.index + 1];
            }
        }
        return -1;
    }
}

Time Complexity

• RLEIterator(int[] A): O(1) — Initializing the object.
• int next(int n): O(k) — In the worst case, we might have to traverse through all the k elements of A.
  • If the RLEIterator exhausts multiple sections of count pairs, the operation complexity grows with the number of sections exhausted.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?