LeetCode 284 - Peeking Iterator

Difficulty: 🟡 Medium
Topics: Array, Design, Iterator

Solution

Problem Understanding

The problem asks us to extend the functionality of a standard iterator with an additional peek operation. A standard iterator provides two operations: next(), which returns the next element in the sequence and advances the pointer, and hasNext(), which tells whether there are more elements left. The PeekingIterator enhances this interface with peek(), which returns the next element without advancing the iterator.

The input is an iterator over a list of integers, and the output is the sequence of results produced by calls to next, peek, and hasNext. We are guaranteed that all calls are valid, so next will never be called when no elements remain. The list size is small, up to 1000 elements, and the number of operations is similarly bounded at 1000. This ensures that even straightforward solutions with O(n) space are acceptable.

Important edge cases include iterators with a single element, sequences where multiple peek calls occur before a next, and the situation where the iterator is exhausted. Handling these correctly requires careful tracking of the "next" element without consuming it prematurely.

Approaches

The brute-force approach would be to simply rely on the underlying iterator for every operation. For peek(), we could repeatedly call next() and then somehow store the consumed element to allow it to be returned again. This would be inefficient and error-prone because peek might require multiple manipulations of the iterator state, which could introduce bugs and unnecessary overhead.

The optimal approach is to maintain a buffer of the next element. We store the next element in a private variable during initialization and update it every time next() is called. This allows peek() to simply return the buffered value without advancing, next() to return the buffered value and then refill it, and hasNext() to check if the buffer is None. This approach keeps operations clean, O(1) time per operation, and requires only O(1) extra space for the buffer.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per peek	O(n)	Repeatedly advances iterator for peek, potentially storing elements
Optimal	O(1) per operation	O(1)	Maintains a buffer for the next element to support peek efficiently

Algorithm Walkthrough

Initialize the PeekingIterator with an iterator object. During initialization, check if the iterator has a next element and, if so, store it in a buffer called next_element.
Implement peek() to simply return the value stored in next_element. This guarantees the iterator state is not advanced.
Implement next() to first return the value in next_element. Then, check if the underlying iterator has another element. If it does, update next_element with the new value; otherwise, set it to None.
Implement hasNext() to return True if next_element is not None, which indicates that there are more elements to iterate.

Why it works: The invariant maintained is that next_element always holds the next value to be returned. This ensures that peek() is always correct, next() updates the buffer correctly, and hasNext() accurately reflects whether iteration can continue.

Python Solution

class PeekingIterator:
    def __init__(self, iterator: 'Iterator'):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iterator = iterator
        self.next_element = iterator.next() if iterator.hasNext() else None

    def peek(self) -> int:
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        return self.next_element

    def next(self) -> int:
        """
        :rtype: int
        """
        current = self.next_element
        self.next_element = self.iterator.next() if self.iterator.hasNext() else None
        return current

    def hasNext(self) -> bool:
        """
        :rtype: bool
        """
        return self.next_element is not None

In the Python implementation, we maintain self.next_element to store the next value. peek() returns it without advancing, next() returns the buffered value and updates it by calling the underlying iterator if available, and hasNext() simply checks whether the buffer is None. This design ensures O(1) time for each operation and avoids modifying the underlying iterator unnecessarily.

Go Solution

type PeekingIterator struct {
    iter        *Iterator
    nextElement int
    hasNextVal  bool
}

func Constructor(iter *Iterator) *PeekingIterator {
    pi := &PeekingIterator{iter: iter}
    if iter.hasNext() {
        pi.nextElement = iter.next()
        pi.hasNextVal = true
    } else {
        pi.hasNextVal = false
    }
    return pi
}

func (this *PeekingIterator) peek() int {
    return this.nextElement
}

func (this *PeekingIterator) next() int {
    current := this.nextElement
    if this.iter.hasNext() {
        this.nextElement = this.iter.next()
    } else {
        this.hasNextVal = false
    }
    return current
}

func (this *PeekingIterator) hasNext() bool {
    return this.hasNextVal
}

In Go, we handle the next element and a hasNextVal flag separately because Go does not have a None value for integers. This ensures that peek() and next() behave identically to Python. The buffer allows all operations to remain O(1) in time.

Worked Examples

Consider the input [1, 2, 3]. The iterator starts at 1.

Operation	next_element	Return	Notes
peek()	1	1	Returns current buffer
next()	2	1	Updates buffer to next element
peek()	2	2	Buffer unchanged
next()	3	2	Updates buffer to next element
next()	None	3	Buffer exhausted
hasNext()	None	False	No elements left

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per operation	All operations rely on a pre-fetched buffer or the underlying iterator's O(1) operations
Space	O(1)	Only one additional variable is needed for the buffer

The reasoning is that maintaining a buffer guarantees constant time lookups for peek and constant updates for next, and no additional data structures proportional to input size are needed.

Test Cases

# Provided example
nums = [1, 2, 3]
iter = PeekingIterator(Iterator(nums))
assert iter.next() == 1  # next
assert iter.peek() == 2  # peek
assert iter.next() == 2  # next
assert iter.next() == 3  # next
assert iter.hasNext() == False  # no elements left

# Single element
nums = [5]
iter = PeekingIterator(Iterator(nums))
assert iter.peek() == 5  # peek
assert iter.hasNext() == True
assert iter.next() == 5  # next
assert iter.hasNext() == False

# Multiple peeks
nums = [10, 20]
iter = PeekingIterator(Iterator(nums))
assert iter.peek() == 10
assert iter.peek() == 10
assert iter.next() == 10
assert iter.peek() == 20
assert iter.next() == 20
assert iter.hasNext() == False

Test	Why
[1,2,3]	Basic functionality with mixed operations
[5]	Single-element edge case
[10,20]	Multiple peek calls before next to ensure peek does not advance

Edge Cases

One edge case is an iterator with a single element. In this case, peek() and next() should return the same value initially, and hasNext() should correctly return False after consuming the element. Without proper buffering, a naive implementation could fail here.

Another edge case is when multiple peek() calls occur consecutively. A naive solution that consumes elements during peek would return different values or prematurely advance the iterator. Our buffer ensures repeated peek() calls always return the same next element.

A third edge case is when the iterator is completely empty at initialization. hasNext() should immediately return False, and peek() or next() should never be called per constraints. Handling the buffer initialization conditionally prevents any null reference or invalid access errors.