#900

Medium

LeetCode Problem Workspace

RLE Iterator

Design an efficient iterator for a run-length encoded array, handling large counts and sequential access correctly every time.

array design counting iterator

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Maintain Two Pointers

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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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)

Continue Practicing

#284 peeking iterator #911 online election #914 x of a kind in a deck of cards