LeetCode 900: RLE Iterator (Run-Length Consumption Pointer)
LeetCode 900DesignSimulationToday we solve LeetCode 900 - RLE Iterator.
Source: https://leetcode.com/problems/rle-iterator/
English
Problem Summary
We are given a run-length encoded array encoding, where pairs [count, value] describe a sequence. Build an iterator with next(n), which consumes n elements and returns the last consumed value, or -1 if not enough elements remain.
Key Insight
Keep a pointer on run counts (even indices). For each next(n), skip fully exhausted runs and decrement the current run count. Each run is advanced at most once globally, so total work is linear in number of runs.
Algorithm
- Store encoding in-place and keep pointer i at count positions.
- While i is valid and current count < n, subtract and move to next run.
- If pointer is out of range, return -1.
- Otherwise reduce current count by n and return its value.
Complexity Analysis
Amortized time per call: O(1).
Total over all calls: O(k), where k is number of runs.
Space: O(1) extra (excluding input storage).
Common Pitfalls
- Using int and overflowing counts in languages where n can be large.
- Forgetting to move by 2 positions between runs.
- Returning run value too early before exhausting n.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class RLEIterator {
private long[] arr;
private int i;
public RLEIterator(int[] encoding) {
this.arr = new long[encoding.length];
for (int j = 0; j < encoding.length; j++) arr[j] = encoding[j];
this.i = 0;
}
public int next(int n) {
long need = n;
while (i < arr.length && arr[i] < need) {
need -= arr[i];
i += 2;
}
if (i >= arr.length) return -1;
arr[i] -= need;
return (int) arr[i + 1];
}
}type RLEIterator struct {
arr []int64
i int
}
func Constructor(encoding []int) RLEIterator {
a := make([]int64, len(encoding))
for i, v := range encoding {
a[i] = int64(v)
}
return RLEIterator{arr: a, i: 0}
}
func (this *RLEIterator) Next(n int) int {
need := int64(n)
for this.i < len(this.arr) && this.arr[this.i] < need {
need -= this.arr[this.i]
this.i += 2
}
if this.i >= len(this.arr) {
return -1
}
this.arr[this.i] -= need
return int(this.arr[this.i+1])
}class RLEIterator {
vector<long long> arr;
int i = 0;
public:
RLEIterator(vector<int>& encoding) {
arr.assign(encoding.begin(), encoding.end());
}
int next(int n) {
long long need = n;
while (i < (int)arr.size() && arr[i] < need) {
need -= arr[i];
i += 2;
}
if (i >= (int)arr.size()) return -1;
arr[i] -= need;
return (int)arr[i + 1];
}
};class RLEIterator:
def __init__(self, encoding: List[int]):
self.arr = list(map(int, encoding))
self.i = 0
def next(self, n: int) -> int:
need = n
while self.i < len(self.arr) and self.arr[self.i] < need:
need -= self.arr[self.i]
self.i += 2
if self.i >= len(self.arr):
return -1
self.arr[self.i] -= need
return self.arr[self.i + 1]var RLEIterator = function(encoding) {
this.arr = encoding.map(v => BigInt(v));
this.i = 0;
};
/**
* @param {number} n
* @return {number}
*/
RLEIterator.prototype.next = function(n) {
let need = BigInt(n);
while (this.i < this.arr.length && this.arr[this.i] < need) {
need -= this.arr[this.i];
this.i += 2;
}
if (this.i >= this.arr.length) return -1;
this.arr[this.i] -= need;
return Number(this.arr[this.i + 1]);
};中文
题目概述
给定游程编码数组 encoding，每对 [count, value] 表示若干个相同数字。实现迭代器 next(n)，每次消耗 n 个元素，返回这次最后一个被消耗的值；若剩余不足则返回 -1。
核心思路
维护一个指针指向“计数位”（偶数下标）。每次调用时不断跳过已完全消耗的 run，最终在当前 run 内扣减所需数量并返回对应值。每个 run 最多被跳过一次，因此总体线性。
算法步骤
- 保存编码数组并维护指针 i（始终指向 count）。
- 当当前 count 小于 n 时，先扣掉并跳到下一个 run（i += 2）。
- 如果越界，说明不够消耗，返回 -1。
- 否则在当前 run 扣减剩余需求并返回对应 value。
复杂度分析
单次调用摊还时间复杂度：O(1)。
所有调用总计：O(k)（k 为 run 数量）。
额外空间复杂度：O(1)。
常见陷阱
- 使用 32 位整型导致计数相减溢出。
- 指针没有按 2 递增，破坏 pair 对齐。
- 还没扣完 n 就提前返回当前 value。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class RLEIterator {
private long[] arr;
private int i;
public RLEIterator(int[] encoding) {
this.arr = new long[encoding.length];
for (int j = 0; j < encoding.length; j++) arr[j] = encoding[j];
this.i = 0;
}
public int next(int n) {
long need = n;
while (i < arr.length && arr[i] < need) {
need -= arr[i];
i += 2;
}
if (i >= arr.length) return -1;
arr[i] -= need;
return (int) arr[i + 1];
}
}type RLEIterator struct {
arr []int64
i int
}
func Constructor(encoding []int) RLEIterator {
a := make([]int64, len(encoding))
for i, v := range encoding {
a[i] = int64(v)
}
return RLEIterator{arr: a, i: 0}
}
func (this *RLEIterator) Next(n int) int {
need := int64(n)
for this.i < len(this.arr) && this.arr[this.i] < need {
need -= this.arr[this.i]
this.i += 2
}
if this.i >= len(this.arr) {
return -1
}
this.arr[this.i] -= need
return int(this.arr[this.i+1])
}class RLEIterator {
vector<long long> arr;
int i = 0;
public:
RLEIterator(vector<int>& encoding) {
arr.assign(encoding.begin(), encoding.end());
}
int next(int n) {
long long need = n;
while (i < (int)arr.size() && arr[i] < need) {
need -= arr[i];
i += 2;
}
if (i >= (int)arr.size()) return -1;
arr[i] -= need;
return (int)arr[i + 1];
}
};class RLEIterator:
def __init__(self, encoding: List[int]):
self.arr = list(map(int, encoding))
self.i = 0
def next(self, n: int) -> int:
need = n
while self.i < len(self.arr) and self.arr[self.i] < need:
need -= self.arr[self.i]
self.i += 2
if self.i >= len(self.arr):
return -1
self.arr[self.i] -= need
return self.arr[self.i + 1]var RLEIterator = function(encoding) {
this.arr = encoding.map(v => BigInt(v));
this.i = 0;
};
/**
* @param {number} n
* @return {number}
*/
RLEIterator.prototype.next = function(n) {
let need = BigInt(n);
while (this.i < this.arr.length && this.arr[this.i] < need) {
need -= this.arr[this.i];
this.i += 2;
}
if (this.i >= this.arr.length) return -1;
this.arr[this.i] -= need;
return Number(this.arr[this.i + 1]);
};
Comments