Problem

We can use run-length encoding (i.e., RLE) to encode a sequence of integers. In a run-length encoded array of even length encoding (0-indexed), for all even i, encoding[i] tells us the number of times that the non-negative integer value encoding[i + 1] is repeated in the sequence.

  • For example, the sequence arr = [8,8,8,5,5] can be encoded to be encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] and encoding = [2,8,1,8,2,5] are also valid RLE of arr.

Given a run-length encoded array, design an iterator that iterates through it.

Implement the RLEIterator class:

  • RLEIterator(int[] encoded) Initializes the object with the encoded array encoded.
  • int next(int n) Exhausts the next n elements and returns the last element exhausted in this way. If there is no element left to exhaust, return -1 instead.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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.

Input Format

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class RLEIterator {

    public RLEIterator(int[] encoding) {
        
    }
    
    public int next(int n) {
        
    }
}

Solution

Method 1 - Iterator with Pointer and Consumption

Intuition

We maintain a pointer to the current run in the encoding and a counter for how many elements remain in that run. For each next(n) call, we consume elements from the current run, moving to the next run as needed, and return the last value exhausted, or -1 if we run out.

Approach

  • Store the encoding array and a pointer to the current run (index).
  • For each next(n) call:
    • While n > 0 and there are runs left:
      • If the current run has enough elements, consume n and return the value.
      • Otherwise, consume all remaining elements in the current run, subtract from n, and move to the next run.
  • If we run out of runs before exhausting n, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class RLEIterator {
    vector<int> encoding;
    int idx = 0;
public:
    RLEIterator(vector<int>& A) : encoding(A) {}
    int next(int n) {
        while (idx < encoding.size() && n > 0) {
            if (encoding[idx] >= n) {
                encoding[idx] -= n;
                return encoding[idx + 1];
            } else {
                n -= encoding[idx];
                encoding[idx] = 0;
                idx += 2;
            }
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

type RLEIterator struct {
    encoding []int
    idx      int
}

func Constructor(encoding []int) RLEIterator {
    return RLEIterator{encoding, 0}
}

func (it *RLEIterator) Next(n int) int {
    for it.idx < len(it.encoding) && n > 0 {
        if it.encoding[it.idx] >= n {
            it.encoding[it.idx] -= n
            return it.encoding[it.idx+1]
        }
        n -= it.encoding[it.idx]
        it.idx += 2
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class RLEIterator {
    private int[] encoding;
    private int idx = 0;

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

    public int next(int n) {
        while (idx < encoding.length && n > 0) {
            if (encoding[idx] >= n) {
                encoding[idx] -= n;
                return encoding[idx + 1];
            } else {
                n -= encoding[idx];
                idx += 2;
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class RLEIterator(private val encoding: IntArray) {
    private var idx = 0

    fun next(n: Int): Int {
        var nLeft = n
        while (idx < encoding.size && nLeft > 0) {
            if (encoding[idx] >= nLeft) {
                encoding[idx] -= nLeft
                return encoding[idx + 1]
            } else {
                nLeft -= encoding[idx]
                idx += 2
            }
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class RLEIterator:
    def __init__(self, encoding: list[int]):
        self.encoding = encoding
        self.idx = 0

    def next(self, n: int) -> int:
        while self.idx < len(self.encoding) and n > 0:
            if self.encoding[self.idx] >= n:
                self.encoding[self.idx] -= n
                return self.encoding[self.idx + 1]
            n -= self.encoding[self.idx]
            self.idx += 2
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

struct RLEIterator {
    encoding: Vec<i32>,
    idx: usize,
}

impl RLEIterator {
    fn new(encoding: Vec<i32>) -> Self {
        RLEIterator { encoding, idx: 0 }
    }
    fn next(&mut self, mut n: i32) -> i32 {
        while self.idx < self.encoding.len() && n > 0 {
            if self.encoding[self.idx] >= n {
                self.encoding[self.idx] -= n;
                return self.encoding[self.idx + 1];
            }
            n -= self.encoding[self.idx];
            self.idx += 2;
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class RLEIterator {
    private encoding: number[];
    private idx: number = 0;

    constructor(encoding: number[]) {
        this.encoding = encoding;
    }

    next(n: number): number {
        while (this.idx < this.encoding.length && n > 0) {
            if (this.encoding[this.idx] >= n) {
                this.encoding[this.idx] -= n;
                return this.encoding[this.idx + 1];
            }
            n -= this.encoding[this.idx];
            this.idx += 2;
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(N) per next(n) call, where N is the number of runs in the encoding (worst case: we skip many runs).
  • 🧺 Space complexity: O(M), where M is the length of the encoding array.