LeetCode 284: Peeking Iterator

Problem Restatement

We are given an existing iterator with these operations:

next()
hasNext()

We need to design a new iterator called PeekingIterator that also supports:

peek()

peek() should return the next element without moving the iterator forward.

That means calling:

peek()

multiple times should always return the same value until:

next()

is called.

The official statement defines peek() as retrieving the next element without advancing the iterator. The wrapped iterator already supports next() and hasNext(). (leetcode.com)

Input and Output

Class shape:

class PeekingIterator:
    def __init__(self, iterator):
        ...

    def peek(self):
        ...

    def next(self):
        ...

    def hasNext(self):
        ...

Examples

Suppose the underlying iterator contains:

[1, 2, 3]

Calls behave like this:

The important behavior is:

peek()

does not consume the element.

First Thought: Call next() Inside peek()

A naive idea is:

def peek(self):
    return self.iterator.next()

But this is incorrect.

Calling:

next()

advances the iterator.

So after one peek(), the element would already be consumed.

Example:

peek() -> 1
next() -> 2

This violates the required behavior.

We need a way to remember the next value before it is consumed.

Key Insight

Always cache the next element.

When the PeekingIterator is created:

1. Read the first value from the underlying iterator.
2. Store it in a variable called next_value.

Now:

peek()

simply returns the cached value.

When:

next()

is called:

1. Return the cached value.
2. Advance the underlying iterator once.
3. Update the cache.

So the cache always stores the next unread value.

Algorithm

During initialization:

If the underlying iterator has another value:

self.next_value = iterator.next()

Otherwise:

self.next_value = None

For peek():

return self.next_value

For next():

1. Save the current cached value.
2. Advance the wrapped iterator.
3. Refresh the cache.
4. Return the saved value.

For hasNext():

return self.next_value is not None

Correctness

At all times, next_value stores the next unread element from the underlying iterator, or None if no elements remain.

During initialization, the algorithm reads the first unread element and stores it in next_value. So the invariant holds initially.

peek() simply returns next_value without changing either the cache or the underlying iterator. Therefore the iterator position remains unchanged.

When next() is called, the algorithm returns the current cached value. This is exactly the next unread element.

Then the algorithm advances the wrapped iterator once and updates the cache to the following unread element, or None if no element remains.

So after every operation, next_value continues to store the next unread element.

Therefore:

• peek() always returns the correct next element without consuming it.
• next() always returns the correct next element and advances exactly once.
• hasNext() correctly reports whether unread elements remain.

Complexity

Implementation

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

        if iterator.hasNext():
            self.next_value = iterator.next()
        else:
            self.next_value = None

    def peek(self):
        return self.next_value

    def next(self):
        value = self.next_value

        if self.iterator.hasNext():
            self.next_value = self.iterator.next()
        else:
            self.next_value = None

        return value

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

Code Explanation

We store the wrapped iterator:

self.iterator = iterator

Then we preload the first unread value:

if iterator.hasNext():
    self.next_value = iterator.next()

This creates the cache.

If no value exists:

self.next_value = None

The peek() method simply returns the cached value:

return self.next_value

without advancing anything.

In next():

value = self.next_value

stores the value we will return.

Then we refresh the cache:

if self.iterator.hasNext():
    self.next_value = self.iterator.next()
else:
    self.next_value = None

Finally:

return value

returns the old cached element.

hasNext() checks whether the cache still contains an unread value:

return self.next_value is not None

Alternative Lazy Peek Design

Another design delays caching until the first peek() call.

This uses an additional flag:

self.has_peeked

and only fetches the value when needed.

However, the eager preload version is simpler because:

• peek() becomes trivial.
• hasNext() becomes simple.
• State transitions are easier to reason about.

So the preload cache design is usually preferred.

Testing

class Iterator:
    def __init__(self, nums):
        self.nums = nums
        self.index = 0

    def hasNext(self):
        return self.index < len(self.nums)

    def next(self):
        value = self.nums[self.index]
        self.index += 1
        return value

def test_peeking_iterator():
    it = PeekingIterator(Iterator([1, 2, 3]))

    assert it.peek() == 1
    assert it.peek() == 1

    assert it.next() == 1
    assert it.next() == 2

    assert it.peek() == 3
    assert it.hasNext() is True

    assert it.next() == 3
    assert it.hasNext() is False

    print("all tests passed")

test_peeking_iterator()

Test meaning: