
Problem Statement
The task is to design a special iterator, termed PeekingIterator
, that extends the functionality of a standard iterator by adding a peek
method. This class will be built upon an existing iterator structure and will provide the next element in the sequence without advancing the iterator's position. The PeekingIterator
class includes several operations:
- Initialization: Takes an iterator over integers as input and prepares the
PeekingIterator
instance. - next(): Retrieves the next element in the iterator and moves the internal cursor to the subsequent element, very similar to the typical iterator's
next
method. - hasNext(): Checks if there are still elements left to be iterated over.
- peek(): Returns the upcoming element without advancing the iterator, allowing a look-ahead without disturbing the iteration sequence.
This functionality is particularly useful in scenarios where decision-making depends on the upcoming element without necessarily moving past it.
Examples
Example 1
Input:
["PeekingIterator", "next", "peek", "next", "next", "hasNext"] [[[1, 2, 3]], [], [], [], [], []]
Output:
[null, 1, 2, 2, 3, false]
Explanation:
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); peekingIterator.next(); // return 1, pointer moves to next peekingIterator.peek(); // return 2, pointer does not move peekingIterator.next(); // return 2, pointer moves to next peekingIterator.next(); // return 3, pointer moves to next peekingIterator.hasNext(); // return False
Constraints
1 <= nums.length <= 1000
1 <= nums[i] <= 1000
- All the calls to
next
andpeek
are valid. - At most
1000
calls will be made tonext
,hasNext
, andpeek
.
Approach and Intuition
To implement the PeekingIterator
, we simulate the normal behavior of an iterator while adding a buffer to store the result of a peek
operation.
Constructor Initialization:
- The
PeekingIterator
receives a reference to the original iterator and immediately fetches the first value, storing it in a buffer. - A boolean flag indicates whether the buffer is populated.
- The
peek()
Method:- Simply return the value in the buffer without advancing the iterator.
next()
Method:- Return the buffered value.
- Fetch the next value from the underlying iterator to refill the buffer.
hasNext()
Method:- Return whether the buffer still holds a valid value.
This design ensures that the peek
operation has no side effects on the traversal sequence, enabling the user to preview the next value safely without altering the iterator’s internal state. The buffer acts as a one-element lookahead, which is updated only when next()
is called.
Solutions
- Java
import java.util.NoSuchElementException;
class AdvancedIterator implements Iterator<Integer> {
private Iterator<Integer> baseIterator;
private Integer upcomingElement = null;
public AdvancedIterator(Iterator<Integer> iterator) {
if (iterator.hasNext()) {
upcomingElement = iterator.next();
}
baseIterator = iterator;
}
public Integer peek() {
return upcomingElement;
}
@Override
public Integer next() {
if (upcomingElement == null) {
throw new NoSuchElementException();
}
Integer currentValue = upcomingElement;
upcomingElement = null;
if (baseIterator.hasNext()) {
upcomingElement = baseIterator.next();
}
return currentValue;
}
@Override
public boolean hasNext() {
return upcomingElement != null;
}
}
The provided Java solution introduces an AdvancedIterator
class that extends the functionality of a standard Iterator<Integer>
by allowing an element to be previewed without advancing the iterator. This is particularly useful in scenarios where you want to inspect elements before deciding to move the iterator forward.
Structure Explanation:
- The
AdvancedIterator
class maintains a privatebaseIterator
which is the original iterator provided during instantiation. - An additional
Integer
field,upcomingElement
, is used to hold the next element from the base iterator. This allows the peek operation to be implemented.
- The
Constructor:
- Initializes the iterator and pre-fetches the first element if available. This pre-fetching ensures that
peek()
can immediately return the next element without altering the state of the iterator.
- Initializes the iterator and pre-fetches the first element if available. This pre-fetching ensures that
Method
peek()
:- Returns the next element without removing it from the iterator. This method allows you to look ahead at the next item without actually moving the iterator.
Method
next()
:- Returns the current element and advances the iterator. This method behaves like the standard
next()
method but also manages theupcomingElement
for subsequent calls. - Throws
NoSuchElementException
if no elements are left, ensuring proper handling of the iterator's bounds.
- Returns the current element and advances the iterator. This method behaves like the standard
Method
hasNext()
:- Returns a boolean indicating whether there are more elements to iterate. This is determined by checking the presence of an
upcomingElement
.
- Returns a boolean indicating whether there are more elements to iterate. This is determined by checking the presence of an
This implementation seamlessly adds the peek functionality to the iterator pattern, enhancing its capabilities while keeping the familiar behavior of standard Java iterators. The class ensures that all usual iterator operations are supported, including robust exception handling for boundary conditions.
No comments yet.