How to Solve RLE Iterator

This problem requires building a custom iterator over a run-length encoded sequence. You must track which values remain and how many times each is repeated, returning the next elements correctly on demand. Careful handling of large counts and sequential consumption is key to avoiding off-by-one errors or index overflows while maintaining efficient operations.

Problem Statement

You are given a run-length encoded array where even indices represent counts and odd indices represent values. Implement an iterator that returns the next n elements in sequence, respecting the repetition counts in the encoding.

Implement the RLEIterator class that supports next(n) returning the next element in the expanded sequence, or -1 if the requested elements exceed the sequence length. Ensure your solution handles large counts efficiently without constructing the full expanded array.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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.

Solution Approach

Track Remaining Counts with Pointer

Maintain an index pointer on the encoding array and subtract from the count at even indices as elements are consumed. Move the pointer forward whenever the current count reaches zero, ensuring next(n) always returns the correct element without expanding the array.

Handle Large n Efficiently

Instead of expanding the array, repeatedly decrement the requested n from the current count. If n exceeds the current count, reduce n accordingly and advance to the next pair in the encoding. This prevents memory overload and supports counts up to 10^9.

Return -1 on Exhaustion

If the pointer reaches the end of the encoding array before fully consuming n, immediately return -1. This guarantees correct behavior for sequences shorter than the requested number of elements, matching the problem's sequential exhaustion pattern.

Complexity Analysis

Time complexity is O(k) per call to next, where k is the number of encoding segments traversed; space complexity is O(1) since the iterator uses the original encoding without expansion.

What Interviewers Usually Probe

• Expecting in-place iteration without full sequence expansion.
• Watch for off-by-one errors in large counts.
• Check handling of next(n) when n exceeds remaining elements.

Common Pitfalls or Variants

Common pitfalls

• Trying to expand the full sequence causing memory issues.
• Failing to update the pointer correctly after exhausting counts.
• Returning incorrect values when next(n) exceeds remaining elements.

Follow-up variants

• Implement a peek() method to see the next element without consuming it.
• Support decrementing elements from the sequence dynamically.
• Adapt the iterator for multiple simultaneous sequences with independent pointers.

How GhostInterview Helps

• Automatically tracks remaining counts and pointer positions for each next call.
• Detects off-by-one and exhaustion errors in iterator logic.
• Suggests optimizations for large count handling without full sequence expansion.

Topic Pages

• Array
• Design
• Counting
• Iterator

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the RLE Iterator problem about?

It requires building an iterator over a run-length encoded array that returns the next n elements efficiently without expanding the full sequence.

How do you handle large counts in RLE Iterator?

Decrement n from current counts in-place and move the pointer forward when counts are exhausted, avoiding array expansion and memory issues.

What is the time complexity of next(n)?

Time complexity depends on how many encoding segments are traversed; each next(n) call is O(k) where k is the segments crossed.

Why does next(n) sometimes return -1?

If n elements exceed the remaining sequence length, the iterator cannot return a value, so -1 is returned according to the problem rules.

Can RLE Iterator handle consecutive calls correctly?

Yes, as long as the pointer and remaining counts are tracked accurately, consecutive next calls will correctly return sequence elements until exhaustion.