Peeking Iterator

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 and peek are valid.
• At most 1000 calls will be made to next, hasNext, and peek.

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.

1. 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.

2. peek() Method:

   • Simply return the value in the buffer without advancing the iterator.

3. next() Method:

   • Return the buffered value.
   • Fetch the next value from the underlying iterator to refill the buffer.

4. 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

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;
    }
}