284. Peeking Iterator - Solution & Explanation

Q: Is Peeking Iterator easy or hard?

Peeking Iterator is usually classified as a medium difficulty problem. The logic is simple once you realize you must cache the next element, but many candidates initially break iterator semantics by advancing the iterator during peek().

Q: Peeking Iterator Python/Java solution

In Python or Java, wrap the existing iterator and store the next value in a variable during construction. peek() returns the stored value, next() returns it and fetches the next element from the iterator, and hasNext() checks whether the buffer is empty.

Q: How to solve Peeking Iterator in O(1)?

Store the next element from the iterator in a buffer during initialization. peek() simply returns this buffered value. next() returns the buffer and then advances the iterator to refresh the stored value. This ensures constant-time operations without modifying the original collection.

Q: What is the best approach for Peeking Iterator?

The best approach is maintaining a cached next element (look-ahead buffer). Store the upcoming value from the underlying iterator so peek() returns it without advancing the iterator. When next() is called, return the cached value and fetch the next one. All operations run in O(1) time with O(1) extra space.

Q: Is Peeking Iterator asked at Google/Amazon/Meta?

Peeking Iterator is a common design-style interview question and has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of iterator abstraction, state management, and API design rather than heavy algorithms.

Q: What data structure is used in Peeking Iterator?

The solution primarily uses an iterator abstraction with a single cached variable. The underlying data often comes from an array or list, but the key design pattern is a look-ahead buffer that stores the next element.

Q: What is the time complexity of Peeking Iterator?

Each operation—peek(), next(), and hasNext()—runs in O(1) time. The design only stores one additional variable containing the next element, so the space complexity is O(1). The iterator is traversed exactly once.

The problem

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

Follow up: How would you extend your design to be generic and work with all types, not just integer?

Approach overview

Problem Overview: Design a wrapper around an existing iterator that supports an additional peek() operation. The challenge is returning the next element without advancing the underlying iterator while still supporting the standard next() and hasNext() behavior.

The base iterator already provides sequential access. Your job is to extend it so that you can preview the upcoming value. The key difficulty is ensuring that calling peek() does not consume the element while keeping all operations efficient.

Approach 1: Using Internal Buffer Variable (O(1) time, O(1) space)

Maintain a single buffered variable that always stores the next element from the iterator. During initialization, call next() on the underlying iterator and store the value in this buffer. The peek() method simply returns the buffered value without modifying the iterator state.

When next() is called, return the buffered value and immediately fetch the next element from the underlying iterator to refresh the buffer. If the iterator has no more elements, mark the buffer as empty. hasNext() checks whether the buffer currently holds a value. Each operation runs in constant time and uses only one extra variable.

This approach works well in languages like Python and Java where wrapping an existing iterator object is straightforward. The design keeps state management simple and avoids repeated checks on the underlying data structure.

Approach 2: Iterator with Future Look-ahead (O(1) time, O(1) space)

This design also stores the upcoming element but treats it as a "future" pointer. During construction, advance the underlying iterator once and store the value as the next candidate. The peek() method returns this value directly.

When next() is called, return the stored value and advance the underlying iterator again to update the future pointer. If the iterator has no remaining elements, mark the future pointer as invalid. hasNext() checks whether the future pointer exists.

This pattern is common in system design questions involving design of iterators or streaming APIs. It avoids modifying the original array or collection and keeps operations constant time.

Recommended for interviews: The buffered look-ahead design is the expected solution. Interviewers want to see that you maintain a cached next value so peek() does not advance the iterator. A naive implementation that repeatedly copies elements or re-traverses the structure would break iterator semantics and increase complexity. Demonstrating a constant-time wrapper around the iterator shows strong understanding of iterator design.

Approach 1: Using Internal Buffer Variable

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.

Python

class PeekingIterator:
    def __init__(self, iterator):
        self.iterator = iterator
        self.next_element = next(iterator, None)

    def peek(self):
        return self.next_element

    def next(self):
        current = self.next_element
        self.next_element = next(self.iterator, None)
        return current

    def hasNext(self):
        return self.next_element is not None

Java

import java.util.Iterator;

class PeekingIterator implements Iterator<Integer> {
    private Iterator<Integer> iterator;
    private Integer nextElement;

    public PeekingIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
        if (iterator.hasNext()) {
            nextElement = iterator.next();
        }
    }

    public Integer peek() {
        return nextElement;
    }

    @Override
    public Integer next() {
        Integer current = nextElement;
        nextElement = iterator.hasNext() ? iterator.next() : null;
        return current;
    }

    @Override
    public boolean hasNext() {
        return nextElement != null;
    }
}

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.

Complexity

Time Complexity: O(1) for all operations.
Space Complexity: O(1), as we only store single elements.

Try this approach in the editor

Approach 2: Iterator with Future Look-ahead

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

C++

#include <vector>
using namespace std;

class PeekingIterator : public Iterator {
    int nextElement;
    bool hasPeeked;
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums), hasPeeked(false) {}

    int peek() {
        if (!hasPeeked) {
            nextElement = Iterator::next();
            hasPeeked = true;
        }
        return nextElement;
    }

    int next() {
        if (!hasPeeked) return Iterator::next();
        hasPeeked = false;
        return nextElement;
    }

    bool hasNext() const {
        return hasPeeked || Iterator::hasNext();
    }
};

using System.Collections.Generic;

public class PeekingIterator {
    private IEnumerator<int> iterator;
    private bool hasPeeked;
    private int nextElement;

    public PeekingIterator(IEnumerator<int> iterator) {
        this.iterator = iterator;
        this.hasPeeked = false;
    }

    public int Peek() {
        if (!hasPeeked) {
            iterator.MoveNext();
            nextElement = iterator.Current;
            hasPeeked = true;
        }
        return nextElement;
    }

    public int Next() {
        if (!hasPeeked) {
            iterator.MoveNext();
            return iterator.Current;
        }
        hasPeeked = false;
        return nextElement;
    }

    public bool HasNext() {
        return hasPeeked || iterator.MoveNext();
    }
}

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.

Complexity

Time Complexity: O(1) for all operations.
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Default Approach

/*   Below is the interface for Iterator, which is already defined for you.
 *
 *   type Iterator struct {
 *
 *   }
 *
 *   func (this *Iterator) hasNext() bool {
 *		// Returns true if the iteration has more elements.
 *   }
 *
 *   func (this *Iterator) next() int {
 *		// Returns the next element in the iteration.
 *   }
 */

type PeekingIterator struct {
	iter          *Iterator
	hasPeeked     bool
	peekedElement int
}

func Constructor(iter *Iterator) *PeekingIterator {
	return &PeekingIterator{iter, iter.hasNext(), iter.next()}
}

func (this *PeekingIterator) hasNext() bool {
	return this.hasPeeked || this.iter.hasNext()
}

func (this *PeekingIterator) next() int {
	if !this.hasPeeked {
		return this.iter.next()
	}
	this.hasPeeked = false
	return this.peekedElement
}

func (this *PeekingIterator) peek() int {
	if !this.hasPeeked {
		this.peekedElement = this.iter.next()
		this.hasPeeked = true
	}
	return this.peekedElement
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Internal Buffer Variable	Time Complexity: O(1) for all operations. Space Complexity: O(1), as we only store single elements.
Iterator with Future Look-ahead	Time Complexity: O(1) for all operations. Space Complexity: O(1).
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Internal Buffer Variable	O(1) per operation	O(1)	Standard iterator wrapper design in Python or Java
Iterator with Future Look-ahead	O(1) per operation	O(1)	Clean design for C++ or C# iterators where a cached next element simplifies peek behavior

Frequently asked questions

Is Peeking Iterator easy or hard?

Peeking Iterator is usually classified as a medium difficulty problem. The logic is simple once you realize you must cache the next element, but many candidates initially break iterator semantics by advancing the iterator during peek().

Peeking Iterator Python/Java solution

In Python or Java, wrap the existing iterator and store the next value in a variable during construction. peek() returns the stored value, next() returns it and fetches the next element from the iterator, and hasNext() checks whether the buffer is empty.

How to solve Peeking Iterator in O(1)?

Store the next element from the iterator in a buffer during initialization. peek() simply returns this buffered value. next() returns the buffer and then advances the iterator to refresh the stored value. This ensures constant-time operations without modifying the original collection.

What is the best approach for Peeking Iterator?

The best approach is maintaining a cached next element (look-ahead buffer). Store the upcoming value from the underlying iterator so peek() returns it without advancing the iterator. When next() is called, return the cached value and fetch the next one. All operations run in O(1) time with O(1) extra space.

Is Peeking Iterator asked at Google/Amazon/Meta?

Peeking Iterator is a common design-style interview question and has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of iterator abstraction, state management, and API design rather than heavy algorithms.

What data structure is used in Peeking Iterator?

The solution primarily uses an iterator abstraction with a single cached variable. The underlying data often comes from an array or list, but the key design pattern is a look-ahead buffer that stores the next element.

What is the time complexity of Peeking Iterator?

Each operation—peek(), next(), and hasNext()—runs in O(1) time. The design only stores one additional variable containing the next element, so the space complexity is O(1). The iterator is traversed exactly once.

Peeking Iterator solution and explanation

The problem

Approach overview

Approach 1: Using Internal Buffer Variable

Approach 2: Iterator with Future Look-ahead

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Peeking Iterator solution and explanation

The problem

Approach overview

Approach 1: Using Internal Buffer Variable

Approach 2: Iterator with Future Look-ahead

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems