RLE Iterator

Medium
2059.

RLE Iterator

RLE Iterator is a medium coding problem on arrays and counting, asked in Google interviews.

A sequence of integers can be stored compactly with run-length encoding: an even-length array encoding where, for every even index i, the value encoding[i + 1] appears encoding[i] times in a row. For example [3,8,0,9,2,5] stands for [8,8,8,5,5] — three 8s, no 9s, two 5s. A run with a count of 0 contributes nothing.

Write the class RLEIterator that walks such a sequence without expanding it:

  • RLEIterator(int[] encoding) starts at the beginning of the sequence that encoding describes.
  • int next(int n) consumes the next n elements and returns the last one consumed. If fewer than n elements are left, it consumes all of them and returns -1.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input
["RLEIterator","next","next","next","next"] [[[2,4,0,7,3,1]],[1],[2],[2],[1]]
Output
[null,4,1,1,-1]
Explanation
The sequence is [4,4,1,1,1]. next(1) consumes one 4 and returns 4. next(2) consumes the other 4 and a 1, returning 1. Only one 1 is left, so next(2) consumes it and returns -1; after that nothing remains and next(1) is -1 too.

Example 2

Input
["RLEIterator","next","next","next"] [[[0,9,1000000000,5]],[999999999],[1],[1]]
Output
[null,5,5,-1]
Explanation
The run of 9s is empty. The sequence is a billion 5s: the first call consumes all but one and returns 5, the second consumes the last 5, and the third finds nothing left.

Constraints

  • 2 <= encoding.length <= 1000
  • encoding.length is even
  • 0 <= encoding[i] <= 10^9
  • 1 <= n <= 10^9
  • At most 1000 calls are made to next
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} encoding
 */
var RLEIterator = function(encoding) {
    
};

/**
 * @param {number} n
 * @return {number}
 */
RLEIterator.prototype.next = function(n) {
    
};

Sign in to run your own test cases

Sign in

RLE Iterator — Solution in Python, Java & C++

RLE Iterator solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Google.

RLE Iterator is a medium coding problem on arrays and counting, asked in Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Counting
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A sequence of integers can be stored compactly with run-length encoding: an even-length array encoding where, for every even index i, the value encoding[i + 1] appears encoding[i] times in a row. For example [3,8,0,9,2,5] stands for [8,8,8,5,5] — three 8s, no 9s, two 5s. A run with a count of 0 contributes nothing.

Write the class RLEIterator that walks such a sequence without expanding it:

  • RLEIterator(int[] encoding) starts at the beginning of the sequence that encoding describes.
  • int next(int n) consumes the next n elements and returns the last one consumed. If fewer than n elements are left, it consumes all of them and returns -1.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["RLEIterator","next","next","next","next"]
[[[2,4,0,7,3,1]],[1],[2],[2],[1]]
Output: [null,4,1,1,-1]
Explanation: The sequence is [4,4,1,1,1]. next(1) consumes one 4 and returns 4. next(2) consumes the other 4 and a 1, returning 1. Only one 1 is left, so next(2) consumes it and returns -1; after that nothing remains and next(1) is -1 too.

Example 2

Input: ["RLEIterator","next","next","next"]
[[[0,9,1000000000,5]],[999999999],[1],[1]]
Output: [null,5,5,-1]
Explanation: The run of 9s is empty. The sequence is a billion 5s: the first call consumes all but one and returns 5, the second consumes the last 5, and the third finds nothing left.

Constraints

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

Hints for RLE Iterator

  1. Hint 1

    The counts can be a billion, so the sequence can never be written out. Work with the runs themselves.

  2. Hint 2

    Keep a pointer to the current run and treat its count as "how many of this value are still unread".

  3. Hint 3

    For next(n): while n is larger than the current run's remaining count, subtract that count from n and move to the next run. If you run out of runs, return -1; otherwise take n from the current run and return its value.

How to solve RLE Iterator

Never expand the encoding. Keep a pointer i to the current run and let encoding[i] mean "elements of this run not yet consumed"; a call to next eats whole runs until the remainder fits inside one.

Approach

  1. Copy the encoding and set i = 0.
  2. next(n): while i is inside the array and n > encoding[i], do n -= encoding[i] and i += 2 — that run is used up entirely (empty runs pass through here too).
  3. If i ran past the end, fewer than n elements were left: return -1 (they are all consumed now, so every later call returns -1 as well).
  4. Otherwise n <= encoding[i]: subtract n from the run and return its value encoding[i + 1].

Why it works

The loop consumes exactly the elements before the one that ends this call: a run is skipped only when all of it is needed, and the call stops in the first run that still holds at least n elements, whose value is therefore the last element consumed. Leaving the remainder in encoding[i] makes the next call start exactly where this one stopped.

Complexity

  • Time — O(r + q) over the whole session for r runs and q calls — the pointer only moves forward
  • Space — O(r) for the copy

Pitfalls

  • Expanding the runs into a list runs out of memory: a single count can be 10^9.
  • The comparison is n > count, not >=: when n equals the remaining count, the call ends inside this run and returns its value.
  • After a call returns -1 the iterator is exhausted; the pointer is already past the end, so nothing extra is needed.

Reference solution

Python

class RLEIterator:

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

    def next(self, n: int) -> int:
        enc = self.enc
        while self.i < len(enc) and n > enc[self.i]:
            n -= enc[self.i]  # this whole run is consumed
            self.i += 2
        if self.i >= len(enc):
            return -1
        enc[self.i] -= n
        return enc[self.i + 1]

Java

class RLEIterator {
    private int[] enc;
    private int i = 0;

    public RLEIterator(int[] encoding) {
        enc = encoding.clone();
    }

    public int next(int n) {
        while (i < enc.length && n > enc[i]) {
            n -= enc[i]; // this whole run is consumed
            i += 2;
        }
        if (i >= enc.length) return -1;
        enc[i] -= n;
        return enc[i + 1];
    }
}

C++

class RLEIterator {
    vector<int> enc;
    size_t i = 0;
public:
    RLEIterator(vector<int>& encoding) : enc(encoding) {}

    int next(int n) {
        while (i < enc.size() && n > enc[i]) {
            n -= enc[i]; // this whole run is consumed
            i += 2;
        }
        if (i >= enc.size()) return -1;
        enc[i] -= n;
        return enc[i + 1];
    }
};

JavaScript

var RLEIterator = function(encoding) {
    this.enc = encoding.slice();
    this.i = 0;
};

RLEIterator.prototype.next = function(n) {
    var enc = this.enc;
    while (this.i < enc.length && n > enc[this.i]) {
        n -= enc[this.i]; // this whole run is consumed
        this.i += 2;
    }
    if (this.i >= enc.length) return -1;
    enc[this.i] -= n;
    return enc[this.i + 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays