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 iterator iterator.int next() Returns the next element in the array and moves the pointer to the next element.boolean hasNext() Returns true if there are still elements in the array.int peek() Returns the next element in the array without moving the pointer.Note: Each language may have a different implementation of the constructor and Iterator, but they all support the int next() and boolean hasNext() functions.
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]); // [1,2,3] peekingIterator.next(); // return 1, the pointer moves to the next element [1,2,3]. peekingIterator.peek(); // return 2, the pointer does not move [1,2,3]. peekingIterator.next(); // return 2, the pointer moves to the next element [1,2,3] peekingIterator.next(); // return 3, the pointer moves to the next element [1,2,3] peekingIterator.hasNext(); // return False
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1000next and peek are valid.1000 calls will be made to next, hasNext, and peek.Follow up: How would you extend your design to be generic and work with all types, not just integer?
Problem Overview: You are given a standard iterator that supports next() and hasNext(). Build a wrapper that adds a peek() operation, allowing you to see the next element without advancing the iterator. The key challenge is preserving iterator state while still exposing constant-time operations.
Approach 1: Using Internal Buffer Variable (O(1) per operation, O(1) space)
This approach stores the next element in a small internal buffer. During initialization, call next() once (if available) and cache the value. The peek() method simply returns this cached value without modifying the iterator. When next() is called, return the cached value and immediately fetch the next element from the underlying iterator to refresh the buffer.
The insight: maintain a single "future" value at all times. That eliminates the need to rewind the iterator or copy the entire structure. Each operation performs constant work—either returning the cached value or updating it with a single iterator call. Time complexity is O(1) per method and space complexity is O(1) because only one extra variable is stored. This design pattern is common in design problems where you extend existing interfaces.
Approach 2: Iterator with Future Look-ahead (O(1) per operation, O(1) space)
Another implementation maintains a flag indicating whether a prefetched value exists along with a variable storing that value. The first time peek() is called, the wrapper pulls the next value from the iterator and stores it. Subsequent peek() calls reuse this stored value without advancing the iterator.
When next() executes, it checks whether a prefetched value already exists. If it does, return it and clear the flag. Otherwise, fetch directly from the underlying iterator. This design works well in languages like C++ or C# where iterators behave slightly differently than Python or Java. Operations still run in O(1) time with O(1) extra memory.
The approach demonstrates a classic iterator pattern: prefetching. Instead of modifying the underlying structure, you manage state externally so the wrapper controls when the next value is consumed.
Recommended for interviews: The buffered variable approach is what most interviewers expect. It clearly shows you understand how iterators advance and how to preserve state using a minimal cache. Mentioning the look-ahead variation shows deeper knowledge of array and iterator traversal patterns. Start with the buffered design—it’s concise, efficient, and matches the intended solution.
In this approach, we use an internal buffer variable to store the next element of the iterator. The key idea is to always keep the next element ready in this buffer when operations like `peek` are called. The `peek` method can return this buffered value, and the `next` method will return the buffered value while simultaneously updating the buffer with the new next element from the iterator.
In the Python solution, we use the Python built-in `next` to advance through the iterator and store the upcoming value in `self.next_element`. When `peek()` is called, it returns `self.next_element`. The `next()` method returns the stored `next_element` and updates it to the next element in the iterator. `hasNext()` checks if `self.next_element` is None to determine if there are more elements.
Java
Time Complexity: O(1) for all operations.
Space Complexity: O(1), as we only store single elements.
This approach leverages the iterator's facility by explicitly controlling its movement and caching the result for future references. It reads the next element so that `peek` can access it but avoids advancing through a list prematurely. Operations are efficient with constant time complexity for each of `peek`, `next`, and `hasNext`.
The C++ solution leverages inheritance from the `Iterator` class, and the `hasPeeked` flag is used to track whether the next element has already been fetched. When `peek()` is called, it sets `nextElement` via `Iterator::next()` and `hasPeeked` to `true`. The `next()` function returns `nextElement` if `hasPeeked` is true and resets the flag. `hasNext()` is straightforward, returning `true` if either `hasPeeked` is true or `Iterator::hasNext()` is true.
C#
Time Complexity: O(1) for all operations.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Using Internal Buffer Variable | Time Complexity: O(1) for all operations. |
| Iterator with Future Look-ahead | Time Complexity: O(1) for all operations. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Internal Buffer Variable | O(1) per operation | O(1) | Best general solution. Simple wrapper that always caches the next element. |
| Iterator with Future Look-ahead | O(1) per operation | O(1) | Useful in languages where explicit iterator state management is needed. |
Binary Search Tree Iterator - Leetcode 173 - Python • NeetCode • 49,532 views views
Watch 9 more video solutions →Practice Peeking Iterator with our built-in code editor and test cases.
Practice on FleetCode