Medium
ArrayDesignCountingIterator
Updated Sep 2026

RLE Iterator

Asked at Databricks

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.

Asked At

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.

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

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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

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.