Description
Design an iterator that supports the peek operation on an existing iterator in addition to the hasNext and the next operations.
Implement the PeekingIterator class:
PeekingIterator(Iterator<int> nums)Initializes the object with the given integer iteratoriterator.int next()Returns the next element in the array and moves the pointer to the next element.boolean hasNext()Returnstrueif there are still elements in the array.int peek()Returns the next element in the array without moving the pointer.
Examples:
Example 1:
Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]Solution in Python
We will implement the PeekingIterator class, which wraps around an existing iterator and provides the ability to peek at the next element without advancing the iterator. The class will also implement the typical next() and hasNext() methods for iterators.
Design Overview:
- Iterator Interface: We assume that the base
Iteratorclass provides the methodsnext()andhasNext(). We do not modify this class but wrap it with additional functionality. - Peeking Mechanism: The
PeekingIteratorneeds to cache the next element to support thepeek()functionality without moving the iterator.- If we call
peek(), the class should return the cached next element without advancing the iterator. - If we call
next(), it should return the cached element and then update the cache with the next element from the underlying iterator (if available).
- If we call
Approach:
- Use a variable,
next_element, to store the next value. - Use a boolean flag,
has_peeked, to track if we have cached a value forpeek()(i.e., if we’ve peeked at the next element but not yet consumed it withnext()).
Methods:
__init__(self, iterator): Initializes thePeekingIteratorwith an existing iterator and sets the initial state.peek(self): Returns the next element without advancing the iterator by checking thenext_elementvariable.next(self): Returns the cachednext_elementif available, otherwise gets the next element from the iterator.hasNext(self): Checks if there are more elements in the iterator, considering both the cache and the original iterator.
Python
class PeekingIterator:
def __init__(self, iterator):
"""
Initialize your data structure here.
:type iterator: Iterator
"""
# Store the original iterator
self.iterator = iterator
# This will store the next element for peeking
self.next_element = None
# This flag indicates whether we've peeked ahead or not
self.has_peeked = False
def peek(self):
"""
Returns the next element in the iteration without advancing the iterator.
:rtype: int
"""
# If we haven't peeked yet, fetch the next element and cache it
if not self.has_peeked:
if self.iterator.hasNext():
self.next_element = self.iterator.next()
self.has_peeked = True
# Return the cached next element
return self.next_element
def next(self):
"""
:rtype: int
"""
# If we have already peeked, return the cached element
if self.has_peeked:
result = self.next_element
self.has_peeked = False # Clear the peeked state
self.next_element = None # Clear the cached element
return result
# Otherwise, just return the next element from the iterator
else:
return self.iterator.next()
def hasNext(self):
"""
:rtype: bool
"""
# We have a next element if we have peeked or the iterator has more elements
return self.has_peeked or self.iterator.hasNext()Explanation of Methods:
__init__(self, iterator):- Initializes the object with the given iterator.
self.iterator: stores the provided iterator.self.next_element: stores the next element whenpeek()is called.self.has_peeked: a boolean flag to indicate whether we’ve peeked ahead.
peek(self):- If we haven’t peeked yet, it calls
next()on the iterator to retrieve the next element and caches it inself.next_element. - If
peek()is called multiple times without callingnext(), it will keep returning the cached value.
- If we haven’t peeked yet, it calls
next(self):- If we’ve already peeked (i.e.,
has_peekedisTrue), it returns the cached value, resets the peek state, and clears the cached value. - Otherwise, it directly calls
next()on the underlying iterator to get the next element.
- If we’ve already peeked (i.e.,
hasNext(self):- Returns
Trueif we have either peeked (i.e., there is a cached element) or the underlying iterator still has more elements.
- Returns
Solution in C++
C++
class PeekingIterator : public Iterator {
private:
int nextElement; // To store the next element (for peeking)
bool hasPeeked; // To indicate whether we have peeked at the next element
public:
// Constructor: Initialize PeekingIterator with the given iterator
PeekingIterator(const vector<int>& nums) : Iterator(nums), hasPeeked(false) {
// hasPeeked is initially false because no peek has happened yet
}
// Returns the next element in the iteration without advancing the iterator.
int peek() {
// If we haven't peeked, cache the next element using Iterator's next()
if (!hasPeeked) {
nextElement = Iterator::next();
hasPeeked = true; // Mark that we've peeked at the next element
}
return nextElement; // Return the cached next element
}
// Override the next() method to return the cached value if peek() was called
int next() {
// If we've already peeked, return the cached value and reset the peek flag
if (hasPeeked) {
hasPeeked = false; // Reset the peek flag
return nextElement; // Return the cached value
}
// Otherwise, just return the next element from the iterator
return Iterator::next();
}
// Override the hasNext() method to account for the cached element
bool hasNext() const {
// Return true if we've peeked (there's a cached element) or if the iterator has more elements
return hasPeeked || Iterator::hasNext();
}
};Solution in Javascript
JavaScript
var PeekingIterator = function(iterator) {
// Store the provided iterator
this.iterator = iterator;
// Cache for the next element (for peeking)
this.nextElement = null;
// Boolean flag to indicate if we've already peeked
this.hasPeeked = false;
};
/**
* Returns the next element in the iteration without advancing the iterator.
* @return {number}
*/
PeekingIterator.prototype.peek = function() {
// If we haven't peeked yet, fetch and cache the next element
if (!this.hasPeeked) {
this.nextElement = this.iterator.next();
this.hasPeeked = true;
}
// Return the cached next element
return this.nextElement;
};
/**
* Returns the next element in the iteration and advances the iterator.
* @return {number}
*/
PeekingIterator.prototype.next = function() {
// If we've already peeked, return the cached value and reset the flag
if (this.hasPeeked) {
const result = this.nextElement;
this.hasPeeked = false;
this.nextElement = null;
return result;
}
// Otherwise, just return the next element from the iterator
return this.iterator.next();
};
/**
* Returns true if the iteration has more elements.
* @return {boolean}
*/
PeekingIterator.prototype.hasNext = function() {
// There is a next element if we have peeked or if the iterator has more elements
return this.hasPeeked || this.iterator.hasNext();
};Solution in Java
Java
import java.util.Iterator;
class PeekingIterator implements Iterator<Integer> {
private Iterator<Integer> iterator;
private Integer nextElement; // Cache for the next element
private boolean hasPeeked; // Flag to indicate if we have peeked at the next element
// Constructor that initializes the iterator
public PeekingIterator(Iterator<Integer> iterator) {
this.iterator = iterator; // Store the provided iterator
this.nextElement = null; // Initialize nextElement as null
this.hasPeeked = false; // Initially, we haven't peeked yet
}
// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
// If we haven't peeked yet, fetch and cache the next element
if (!hasPeeked) {
if (iterator.hasNext()) {
nextElement = iterator.next(); // Cache the next element
hasPeeked = true; // Set the peek flag to true
}
}
return nextElement; // Return the cached element
}
// Returns the next element in the iteration and advances the iterator.
@Override
public Integer next() {
// If we've already peeked, return the cached value and reset the flag
if (hasPeeked) {
hasPeeked = false; // Reset the peek flag
Integer result = nextElement; // Return the cached value
nextElement = null; // Clear the cached value
return result;
}
// Otherwise, just return the next element from the iterator
return iterator.next();
}
// Returns true if the iteration has more elements.
@Override
public boolean hasNext() {
// There is a next element if we have peeked or the underlying iterator has more elements
return hasPeeked || iterator.hasNext();
}
}