LeetCode 284: Peeking Iterator (One-Item Lookahead Cache)
LeetCode 284DesignIteratorToday we solve LeetCode 284 - Peeking Iterator.
Source: https://leetcode.com/problems/peeking-iterator/
English
Problem Summary
Implement a wrapper over an existing iterator so that peek() returns the next element without consuming it, while next() and hasNext() still behave correctly.
Key Insight
Keep a one-item cache (nextVal) plus a validity flag (hasPeeked). This cached value is always the next answer for both peek() and next().
Brute Force and Limitations
Trying to rewind the underlying iterator is usually impossible and expensive. A tiny lookahead cache gives O(1) operations and keeps behavior deterministic.
Optimal Algorithm Steps
1) On construction, pull one item if available and mark cache valid.
2) peek() returns cached value only.
3) next() returns cached value, then prefetch the following item.
4) hasNext() is just hasPeeked.
Complexity Analysis
Time per operation: O(1) amortized.
Extra space: O(1).
Common Pitfalls
- Advancing underlying iterator inside peek().
- Forgetting to refresh cache after next().
- Incorrect hasNext() when cache is empty.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class PeekingIterator implements Iterator<Integer> {
private final Iterator<Integer> it;
private Integer nextVal;
private boolean hasPeeked;
public PeekingIterator(Iterator<Integer> iterator) {
it = iterator;
if (it.hasNext()) {
nextVal = it.next();
hasPeeked = true;
}
}
public Integer peek() {
return nextVal;
}
@Override
public Integer next() {
Integer ans = nextVal;
if (it.hasNext()) {
nextVal = it.next();
hasPeeked = true;
} else {
nextVal = null;
hasPeeked = false;
}
return ans;
}
@Override
public boolean hasNext() {
return hasPeeked;
}
}type PeekingIterator struct {
data []int
idx int
}
func Constructor(iter *Iterator) *PeekingIterator {
arr := make([]int, 0)
for iter.hasNext() {
arr = append(arr, iter.next())
}
return &PeekingIterator{data: arr, idx: 0}
}
func (p *PeekingIterator) peek() int {
return p.data[p.idx]
}
func (p *PeekingIterator) next() int {
v := p.data[p.idx]
p.idx++
return v
}
func (p *PeekingIterator) hasNext() bool {
return p.idx < len(p.data)
}class PeekingIterator : public Iterator {
private:
int nextVal;
bool hasPeeked;
public:
PeekingIterator(const vector<int>& nums) : Iterator(nums), hasPeeked(false) {
if (Iterator::hasNext()) {
nextVal = Iterator::next();
hasPeeked = true;
}
}
int peek() {
return nextVal;
}
int next() {
int ans = nextVal;
if (Iterator::hasNext()) {
nextVal = Iterator::next();
hasPeeked = true;
} else {
hasPeeked = false;
}
return ans;
}
bool hasNext() const {
return hasPeeked;
}
};class PeekingIterator:
def __init__(self, iterator):
self.it = iterator
self.has_peeked = self.it.hasNext()
self.next_val = self.it.next() if self.has_peeked else None
def peek(self):
return self.next_val
def next(self):
ans = self.next_val
if self.it.hasNext():
self.next_val = self.it.next()
self.has_peeked = True
else:
self.next_val = None
self.has_peeked = False
return ans
def hasNext(self):
return self.has_peekedvar PeekingIterator = function(iterator) {
this.it = iterator;
this.hasPeeked = this.it.hasNext();
this.nextVal = this.hasPeeked ? this.it.next() : null;
};
PeekingIterator.prototype.peek = function() {
return this.nextVal;
};
PeekingIterator.prototype.next = function() {
const ans = this.nextVal;
if (this.it.hasNext()) {
this.nextVal = this.it.next();
this.hasPeeked = true;
} else {
this.nextVal = null;
this.hasPeeked = false;
}
return ans;
};
PeekingIterator.prototype.hasNext = function() {
return this.hasPeeked;
};中文
题目概述
在已有迭代器之上再包装一层，新增 peek()，要求能查看下一个元素但不消耗它，同时 next() / hasNext() 仍保持正确语义。
核心思路
维护“一位前瞻缓存”：nextVal + hasPeeked。缓存始终代表当前“下一个可返回元素”，所以 peek() 和 next() 都围绕它工作。
暴力解法与不足
如果每次 peek() 都尝试回退底层迭代器，不仅实现复杂，很多迭代器根本不支持回退。前瞻缓存可以把所有接口稳定在 O(1)。
最优算法步骤
1）初始化时预取一个元素到缓存（若存在）。
2）peek() 直接返回缓存。
3）next() 返回缓存，再预取下一个元素。
4）hasNext() 只看缓存是否有效。
复杂度分析
单次操作时间复杂度：O(1)（均摊）。
额外空间复杂度：O(1)。
常见陷阱
- 在 peek() 中推进了底层迭代器。
- next() 之后忘记更新缓存。
- 缓存为空时 hasNext() 判断错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class PeekingIterator implements Iterator<Integer> {
private final Iterator<Integer> it;
private Integer nextVal;
private boolean hasPeeked;
public PeekingIterator(Iterator<Integer> iterator) {
it = iterator;
if (it.hasNext()) {
nextVal = it.next();
hasPeeked = true;
}
}
public Integer peek() {
return nextVal;
}
@Override
public Integer next() {
Integer ans = nextVal;
if (it.hasNext()) {
nextVal = it.next();
hasPeeked = true;
} else {
nextVal = null;
hasPeeked = false;
}
return ans;
}
@Override
public boolean hasNext() {
return hasPeeked;
}
}type PeekingIterator struct {
data []int
idx int
}
func Constructor(iter *Iterator) *PeekingIterator {
arr := make([]int, 0)
for iter.hasNext() {
arr = append(arr, iter.next())
}
return &PeekingIterator{data: arr, idx: 0}
}
func (p *PeekingIterator) peek() int {
return p.data[p.idx]
}
func (p *PeekingIterator) next() int {
v := p.data[p.idx]
p.idx++
return v
}
func (p *PeekingIterator) hasNext() bool {
return p.idx < len(p.data)
}class PeekingIterator : public Iterator {
private:
int nextVal;
bool hasPeeked;
public:
PeekingIterator(const vector<int>& nums) : Iterator(nums), hasPeeked(false) {
if (Iterator::hasNext()) {
nextVal = Iterator::next();
hasPeeked = true;
}
}
int peek() {
return nextVal;
}
int next() {
int ans = nextVal;
if (Iterator::hasNext()) {
nextVal = Iterator::next();
hasPeeked = true;
} else {
hasPeeked = false;
}
return ans;
}
bool hasNext() const {
return hasPeeked;
}
};class PeekingIterator:
def __init__(self, iterator):
self.it = iterator
self.has_peeked = self.it.hasNext()
self.next_val = self.it.next() if self.has_peeked else None
def peek(self):
return self.next_val
def next(self):
ans = self.next_val
if self.it.hasNext():
self.next_val = self.it.next()
self.has_peeked = True
else:
self.next_val = None
self.has_peeked = False
return ans
def hasNext(self):
return self.has_peekedvar PeekingIterator = function(iterator) {
this.it = iterator;
this.hasPeeked = this.it.hasNext();
this.nextVal = this.hasPeeked ? this.it.next() : null;
};
PeekingIterator.prototype.peek = function() {
return this.nextVal;
};
PeekingIterator.prototype.next = function() {
const ans = this.nextVal;
if (this.it.hasNext()) {
this.nextVal = this.it.next();
this.hasPeeked = true;
} else {
this.nextVal = null;
this.hasPeeked = false;
}
return ans;
};
PeekingIterator.prototype.hasNext = function() {
return this.hasPeeked;
};
Comments