MediumArrayDesignCountingIteratorUpdated Sep 2026

900. RLE Iterator

Asked at Databricks

Difficulty

Medium

Time

O(m) total across all calls, whe

Space

O(1) extra space

Pattern

Array

Companies

1

Problem

We are given a run-length encoded (RLE) array called encoding. It always has an even length. For every even index i, encoding[i] is a count, and encoding[i + 1] is the value that repeats that many times.

For example, encoding = [3, 8, 0, 9, 2, 5] means: the value 8 appears 3 times, the value 9 appears 0 times, and the value 5 appears 2 times. So the decoded stream is [8, 8, 8, 5, 5].

Design a class RLEIterator. Its constructor takes the encoding array. Its method next(n) should consume the next n elements of the decoded stream and return the last element consumed. If the stream runs out before n elements are consumed, return -1 instead. Note that even a partial consumption still uses up the elements that did exist.

You do not need to build the full decoded array. Counts can be as large as 10^9, so the array would be far too big. Instead, walk through the count/value pairs and shrink the counts as you go.

Counts and values come in pairs

encoding380925012345Orange cells are counts, green cells are the valuesthey repeat.decoded3 copies of 88885501234The pair (3, 8) expands to three 8s, and (2, 5)expands to two 5s.
Each even index holds a count, the next index holds the value. Here the stream is [8, 8, 8, 5, 5].

Constraints

  • ●2 <= encoding.length <= 1000
  • ●encoding.length is even
  • ●0 <= encoding[i] <= 10^9
  • ●1 <= n <= 10^9
  • ●At most 1000 calls will be made to next

Examples

Example 1
Input["RLEIterator", "next", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output[null, 8, 8, 5, -1]
WhyThe stream is [8, 8, 8, 5, 5]. The first next(2) eats two 8s and returns the last one, 8. The next next(1) eats the last 8 and returns 8. Then next(1) eats one 5 and returns 5. Finally next(2) needs two elements but only one 5 is left, so it returns -1.
Example 2
Input["RLEIterator", "next", "next", "next"] [[[3, 8, 0, 9, 2, 5]], [4], [1], [1]]
Output[null, 5, 5, -1]
Whynext(4) eats 8, 8, 8 and then the first 5, so the last element eaten is 5. next(1) eats the remaining 5 and returns 5. The stream is now empty, so next(1) returns -1.

Asked At

1 companies
CompanyDifficulty
DatabricksMediumView all Databricks questions →

How to Think About It

1

Understanding RLE encoding: [3, 8, 0, 9, 2, 5] means "8 appears 3 times, then 9 appears 0 times, then 5 appears 2 times". Decoded: [8, 8, 8, 5, 5]. The count-value pairs are at indices (0,1), (2,3), (4,5).

2

Data structure: store the encoding array and a pointer i starting at 0. The pointer always points to the current count index (even index). The current value is at i+1.

3

next(n) algorithm:

  1. While n > 0 and i < len(encoding):
    • If encoding[i] >= n: encoding[i] -= n, return encoding[i+1].
    • If encoding[i] < n: n -= encoding[i], encoding[i] = 0, move i to next pair (i += 2).
  2. If i >= len(encoding) and n > 0, return -1 (exhausted).
4

Why modify the encoding in place: each next(n) call consumes counts. By decrementing counts in place, you avoid creating a separate decoded array. This is space-efficient: O(1) extra space.

5

Walkthrough: encoding = [3, 8, 0, 9, 2, 5].

  • next(2): i=0, encoding[0]=3 >= 2. encoding[0] = 1. Return 8.
  • next(1): i=0, encoding[0]=1 >= 1. encoding[0] = 0. Move to i=2.
  • next(1): i=2, encoding[2]=0 < 1. n=0. Move to i=4.
  • next(1): i=4, encoding[4]=2 >= 1. encoding[4] = 1. Return 5.
  • Result so far: [8, 8, 5].
6

Edge cases: zero counts (like the 0 at index 2) must be skipped. Exhausted iterator returns -1. Requesting more elements than available returns -1 and consumes all remaining.

Optimal Approach

Store the encoding array and a pointer i starting at 0. next(n) consumes n elements from the current position:

  1. While n > 0 and i < len(encoding):
    a. If encoding[i] >= n: decrement encoding[i] by n, return encoding[i+1].
    b. If encoding[i] < n: subtract encoding[i] from n, set encoding[i] = 0, advance i by 2.
  2. If exhausted, return -1.

Walkthrough: encoding = [3, 8, 0, 9, 2, 5].

  • next(4): i=0, count=3 < 4. n=1, count=0, i=2. i=2, count=0 < 1. n=1, i=4. i=4, count=2 >= 1. count=1. Return 5. Decoded so far: [8,8,8,5].
  • next(1): i=4, count=1 >= 1. count=0, i=6. Return 5. Decoded: [8,8,8,5,5].
  • next(1): i=6, i >= len(encoding). Return -1.

Time: O(n/p) amortized where p is the number of pairs. Each pair is visited at most once. Space: O(1) extra.

Walk the pairs and shrink the counts

encoding380925012345iStart: i points at count 3 for value 8.after next(4)080915012345i4 elements: eat all three 8s, then one 5. The lastelement eaten is 5.after next(1)080905012345iOne more element eats the last 5 and returns 5. Thestream is now empty.if count >= n: count -= n, return valueelse: n -= count, count = 0, i += 2if i runs off the end: return -1
A pointer i sits on the current count. next(n) eats n elements by subtracting from counts and jumping to the next pair.
ComplexityTime O(m) total across all calls, wheSpace O(1) extra spaceEach pair is passed over at most once over the whole lifetime of the iterator, and we only keep a pointer plus the given array.

What Trips People Up in Real Interviews

1

Forgetting to skip zero-count entries. The encoding can have 0 counts (like [3, 8, 0, 9, 2, 5]). When encoding[i] is 0, you must move to the next pair immediately, not try to return its value.

2

Confusing the count and value positions. Counts are at even indices (0, 2, 4, ...), values at odd indices (1, 3, 5, ...). Double-check which index is which.

3

Not modifying the encoding in place. Some candidates create a separate decoded list, which works but wastes space. The interview expects O(1) space by modifying counts directly.

4

Returning the wrong value when encoding[i] >= n. You must return the value at encoding[i+1], not at encoding[i]. The count is at even index, value at odd index.

5

Forgetting to return -1 when the iterator is exhausted. If all pairs are consumed and n > 0 remains, return -1. Do not return a garbage value or throw an exception unless specified.

Solution Code

O(m) total across all calls, whe time
class RLEIterator:

    def __init__(self, encoding: list[int]):
        self.encoding = encoding
        self.i = 0

    def next(self, n: int) -> int:
        while self.i < len(self.encoding) and n > 0:
            if self.encoding[self.i] >= n:
                self.encoding[self.i] -= n
                return self.encoding[self.i + 1]
            else:
                n -= self.encoding[self.i]
                self.encoding[self.i] = 0
                self.i += 2
        return -1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the RLE Iterator problem?

Design an RLE (Run-Length Encoding) iterator that decodes an encoded stream. The encoding is given as an array `encoding` where even indices (0, 2, 4, ...) represent counts and odd indices (1, 3, 5, ...) represent values. The `next(n)` method returns the next `n` elements from the decoded stream and exhausts counts as it goes.

How do you solve RLE Iterator?

The optimal approach runs in O(m) total across all calls, whe time and O(1) extra space space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask RLE Iterator?

RLE Iterator is asked at Databricks. It is a medium difficulty problem.

What are common mistakes on RLE Iterator?
  • Forgetting to skip zero-count entries. The encoding can have 0 counts (like `[3, 8, 0, 9, 2, 5]`). When `encoding[i]` is 0, you must move to the next pair immediately, not try to return its value.
  • Confusing the count and value positions. Counts are at even indices (0, 2, 4, ...), values at odd indices (1, 3, 5, ...). Double-check which index is which.
  • Not modifying the encoding in place. Some candidates create a separate decoded list, which works but wastes space. The interview expects `O(1)` space by modifying counts directly.
  • Returning the wrong value when `encoding[i] >= n`. You must return the value at `encoding[i+1]`, not at `encoding[i]`. The count is at even index, value at odd index.
  • Forgetting to return -1 when the iterator is exhausted. If all pairs are consumed and `n > 0` remains, return -1. Do not return a garbage value or throw an exception unless specified.