🎨Now live: Try our Free AI Image Generation Feature

Description
The PeekingIterator
class allows you to peek at the next element in an iterator without advancing the iterator. This is useful in scenarios where you need to look ahead at the next element without consuming it. The class implements the basic operations: peek()
, next()
, and hasNext()
.
peek()
: Returns the next element without advancing the iterator.next()
: Returns the next element and advances the iterator.hasNext()
: Returns whether the iterator has more elements.
Intuition
The problem revolves around managing the state of the iterator such that we can look ahead at the next element without actually moving the iterator forward. The main challenge is to ensure that if we peek at an element, we can still retrieve it later with next()
without losing any elements or advancing the iterator prematurely.
Approach
- Internal State:
- Use an internal variable
pk
to store the value of the next element whenpeek()
is called. This prevents the iterator from advancing prematurely. - Use a boolean flag (or anull
check) to track whether the peeked value is currently stored. - peek() Method:
- If there is no stored peek value (
pk
isnull
orNone
), retrieve the next element from the iterator and store it. - Return the stored value. - next() Method:
- If there is a stored peek value, return it and reset the stored value to
null
orNone
. - If there is no stored peek value, simply return the next element from the iterator. - hasNext() Method: - Check if there is a stored peek value or if the iterator has more elements.
Complexity
Time Complexity:
peek()
,next()
, andhasNext()
all run inO(1)
time since they involve simple checks or retrievals from the iterator.
Space Complexity:
O(1)
because only a constant amount of extra space is used to store the peeked value.
Code
C++
class PeekingIterator : public Iterator {
private:
Iterator* it;
int pk;
bool hasPeeked;
public:
PeekingIterator(const vector& nums) : Iterator(nums) {
it = this;
hasPeeked = false;
}
int peek() {
if (!hasPeeked) {
pk = it->next();
hasPeeked = true;
}
return pk;
}
int next() {
if (!hasPeeked) {
return it->next();
}
int ret = pk;
hasPeeked = false;
return ret;
}
bool hasNext() const {
return hasPeeked || it->hasNext();
}
};
Python
class PeekingIterator:
def __init__(self, iterator):
self.it = iterator
self.pk = None
def peek(self):
if self.pk is None:
self.pk = self.it.next()
return self.pk
def next(self):
if self.pk is None:
return self.it.next()
ret = self.pk
self.pk = None
return ret
def hasNext(self):
return self.pk is not None or self.it.hasNext()
Java
class PeekingIterator implements Iterator {
private Iterator it;
private Integer pk;
public PeekingIterator(Iterator iterator) {
this.it = iterator;
this.pk = null;
}
public Integer peek() {
if (pk == null) {
pk = it.next();
}
return pk;
}
@Override
public Integer next() {
if (pk == null) {
return it.next();
}
Integer ret = pk;
pk = null;
return ret;
}
@Override
public boolean hasNext() {
return pk != null || it.hasNext();
}
}
JavaScript
/**
* @param {Iterator} iterator
*/
class PeekingIterator {
constructor(iterator) {
this.it = iterator;
this.pk = null;
}
peek() {
if (!this.pk) this.pk = this.it.next();
return this.pk;
}
next() {
if(!this.pk) return this.it.next();
let t = this.pk;
this.pk = null;
return t;
}
hasNext() {
if(!this.pk) return this.it.hasNext();
return true;
}
}
/**
* Your PeekingIterator object will be instantiated and called as such:
* var obj = new PeekingIterator(arr)
* var param_1 = obj.peek()
* var param_2 = obj.next()
* var param_3 = obj.hasNext()
*/