Code Implementation

class PeekingIterator:
    def __init__(self, iterator):
        self.iterator = iterator
        self._has_next = True
        try:
            self._next = next(self.iterator)
        except StopIteration:
            self._has_next = False
            self._next = None

    def peek(self):
        return self._next

    def next(self):
        if not self._has_next:
            raise StopIteration()
        curr = self._next
        try:
            self._next = next(self.iterator)
        except StopIteration:
            self._has_next = False
            self._next = None
        return curr

    def hasNext(self):
        return self._has_next
      

class PeekingIterator : public Iterator {
    int nextVal;
    bool has_next;
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        if (Iterator::hasNext()) {
            nextVal = Iterator::next();
            has_next = true;
        } else {
            has_next = false;
        }
    }

    int peek() {
        return nextVal;
    }

    int next() {
        int curr = nextVal;
        if (Iterator::hasNext()) {
            nextVal = Iterator::next();
        } else {
            has_next = false;
        }
        return curr;
    }

    bool hasNext() const {
        return has_next;
    }
};
      

class PeekingIterator implements Iterator<Integer> {
    private Iterator<Integer> iterator;
    private Integer nextVal;
    private boolean hasNext;

    public PeekingIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
        if (iterator.hasNext()) {
            nextVal = iterator.next();
            hasNext = true;
        } else {
            hasNext = false;
        }
    }

    public Integer peek() {
        return nextVal;
    }

    @Override
    public Integer next() {
        Integer curr = nextVal;
        if (iterator.hasNext()) {
            nextVal = iterator.next();
        } else {
            hasNext = false;
        }
        return curr;
    }

    @Override
    public boolean hasNext() {
        return hasNext;
    }
}
      

var PeekingIterator = function(iterator) {
    this.iterator = iterator;
    this._hasNext = iterator.hasNext();
    this._next = this._hasNext ? iterator.next() : null;
};

PeekingIterator.prototype.peek = function() {
    return this._next;
};

PeekingIterator.prototype.next = function() {
    let curr = this._next;
    this._hasNext = this.iterator.hasNext();
    this._next = this._hasNext ? this.iterator.next() : null;
    return curr;
};

PeekingIterator.prototype.hasNext = function() {
    return this._hasNext;
};
      

Problem Description

The Peeking Iterator problem asks you to design an iterator class that supports not only the standard next() and hasNext() operations, but also a peek() operation. The peek() method should return the next element in the iteration without advancing the iterator.

• You are given an iterator to a list of integers.
• Implement a class PeekingIterator that wraps this iterator and supports the following methods:
  • peek(): Returns the next element in the iterator without advancing it.
  • next(): Returns the next element and advances the iterator.
  • hasNext(): Returns whether the iterator has more elements.
• Do not modify the original iterator or the underlying data structure.
• All methods should run in O(1) time.

Thought Process

At first glance, the problem seems straightforward: just call next() on the underlying iterator when needed. However, the challenge is with the peek() operation, which requires us to look at the next element without moving the iterator forward.

If we call next() to get the value for peek(), we have already advanced the iterator, which is not allowed. We need a way to "see" the next value and remember it for both peek() and next() calls. This is a classic "look ahead" problem, which can be solved by caching the next value.

The brute-force idea would be to reconstruct the iterator or underlying list each time, but this is inefficient and breaks the O(1) time requirement. Instead, we can store the next value in a variable whenever we advance, and use that for both peek() and next().

Solution Approach

• Step 1: Initialize the PeekingIterator
  • When the PeekingIterator is created, immediately advance the underlying iterator once and store the value in a variable (let's call it _next).
  • Maintain a flag (e.g., _has_next) to indicate whether there are more elements.
• Step 2: Implement peek()
  • Simply return the cached _next value.
• Step 3: Implement next()
  • Return the cached _next value.
  • Advance the underlying iterator by one step and update _next and _has_next.
• Step 4: Implement hasNext()
  • Return the _has_next flag.

This approach ensures that all operations are O(1) and that peek() never modifies the iterator state.

Example Walkthrough

Suppose the input iterator is over the list [1, 2, 3].

1. Initialization:
   • Call next() on the underlying iterator and store 1 in _next.
   • _has_next is True (since there are more elements).
2. First peek() call:
   • Return 1 (value of _next).
3. First next() call:
   • Return 1.
   • Advance the iterator and store 2 in _next.
4. Second peek() call:
   • Return 2.
5. Second next() call:
   • Return 2.
   • Advance the iterator and store 3 in _next.
6. Third peek() call:
   • Return 3.
7. Third next() call:
   • Return 3.
   • No more elements; set _has_next to False.
8. Further hasNext() calls:
   • Return False.

At no point does peek() advance the iterator; only next() does.

Time and Space Complexity

• Brute-force approach:
  • If you tried to reconstruct the iterator or underlying list for each peek(), each operation could be O(n), which is too slow.
• Optimized approach (our solution):
  • All methods (peek(), next(), hasNext()) run in O(1) time because they only access or update a cached value and a flag.
  • Space complexity is O(1) because we only store one extra value and a flag, regardless of the size of the input.

Summary

The Peeking Iterator problem is a classic example of using a "lookahead" buffer to extend the functionality of an iterator. By caching the next value and maintaining a simple flag, we can efficiently support peeking at the next element without advancing, while keeping all operations at constant time and space. This approach is elegant, efficient, and demonstrates the power of careful state management in iterator design.