Problem Description

This problem asks you to enhance a standard iterator with an additional peek functionality. You need to design a PeekingIterator class that wraps around an existing iterator and provides three operations:

1. next(): Returns the next element in the sequence and advances the iterator to the following element.

2. hasNext(): Returns true if there are more elements remaining in the sequence, false otherwise.

3. peek(): Returns the next element in the sequence without advancing the iterator. This means calling peek() multiple times in a row should return the same element, and the iterator position should remain unchanged.

The key challenge is implementing peek() since the underlying iterator only provides next() (which advances) and hasNext() operations. You need to figure out how to "look ahead" at the next element without consuming it from the original iterator.

For example, if you have an iterator over [1, 2, 3]:

• Calling peek() returns 1 but keeps the iterator at position 1
• Calling peek() again still returns 1
• Calling next() returns 1 and advances to position 2
• Calling peek() now returns 2 without advancing
• Calling next() returns 2 and advances to position 3

The solution uses a caching strategy: when peek() is called, it fetches the next element from the underlying iterator using next() and stores it in peeked_element. A flag has_peeked tracks whether we have a cached element. Subsequent calls to next() return this cached element instead of calling the underlying iterator's next() method.

Intuition

The main challenge is that the underlying iterator's next() method is destructive - once you call it, the element is consumed and the iterator moves forward. But peek() needs to show us the next element without consuming it.

Think of it like a queue of people where you can only see and remove the person at the front. If someone asks "who's next?" without wanting to remove them, you'd need to temporarily remove the person, remember who they are, and then handle them specially when someone actually wants to remove the next person.

This leads us to a caching approach: we need to "pre-fetch" the next element when peek() is called. Since we've already consumed this element from the underlying iterator, we must store it somewhere until next() is actually called.

The key insight is maintaining two pieces of state:

1. peeked_element: Stores the pre-fetched element when peek() is called
2. has_peeked: A boolean flag indicating whether we have a cached element

When peek() is called, we check if we've already peeked. If not, we fetch the next element from the iterator and cache it. If we have already peeked, we just return the cached value.

When next() is called, we need to consider two cases:

• If we have a cached element (from a previous peek()), return it and clear the cache
• If we don't have a cached element, directly call the underlying iterator's next()

For hasNext(), we need to return true if either we have a cached element OR the underlying iterator has more elements. This ensures consistency - if peek() was successful, then hasNext() should return true.

This design elegantly handles all edge cases and maintains the iterator's expected behavior while adding the peek functionality with minimal overhead.

Solution Approach

The implementation uses a wrapper pattern with caching to add peek functionality to an existing iterator. Here's how each component works:

Data Structure:

• self.iterator: Stores reference to the underlying iterator
• self.has_peeked: Boolean flag indicating if we've cached an element
• self.peeked_element: Stores the cached element when peek is called

Constructor (__init__):

def __init__(self, iterator):
    self.iterator = iterator
    self.has_peeked = False
    self.peeked_element = None

Initializes the wrapper with the underlying iterator and sets up the caching mechanism with has_peeked as False initially.

peek() Method:

def peek(self):
    if not self.has_peeked:
        self.peeked_element = self.iterator.next()
        self.has_peeked = True
    return self.peeked_element

• If we haven't peeked yet (not self.has_peeked), fetch the next element from the underlying iterator using self.iterator.next()
• Cache this element in self.peeked_element and set self.has_peeked = True
• Return the cached element
• If we've already peeked, simply return the cached self.peeked_element

next() Method:

def next(self):
    if not self.has_peeked:
        return self.iterator.next()
    result = self.peeked_element
    self.has_peeked = False
    self.peeked_element = None
    return result

• If we haven't peeked (not self.has_peeked), directly return self.iterator.next()
• If we have peeked, return the cached element and reset the cache by setting self.has_peeked = False and self.peeked_element = None

hasNext() Method:

def hasNext(self):
    return self.has_peeked or self.iterator.hasNext()

Returns True if either:

• We have a cached element (self.has_peeked is True), OR
• The underlying iterator has more elements (self.iterator.hasNext())

This implementation ensures that:

1. Multiple consecutive peek() calls return the same value
2. A next() after peek() returns the peeked value
3. The iterator behaves normally when peek() isn't used
4. Memory overhead is minimal - at most one element is cached at any time

Example Walkthrough

Let's walk through a concrete example with the sequence [1, 2, 3]:

Initial State:

• iterator points to [1, 2, 3]
• has_peeked = False
• peeked_element = None

Operation 1: peek()

• Since has_peeked = False, we call iterator.next() which returns 1
• Cache it: peeked_element = 1
• Set has_peeked = True
• Return 1
• State: iterator now points to [2, 3], but we have 1 cached

Operation 2: peek() again

• Since has_peeked = True, we don't call the iterator
• Simply return peeked_element = 1
• State remains unchanged

Operation 3: hasNext()

• Check: has_peeked is True, so return True
• (Even without checking iterator.hasNext(), we know we have an element)

Operation 4: next()

• Since has_peeked = True, we return the cached peeked_element = 1
• Clear cache: has_peeked = False, peeked_element = None
• Return 1
• State: iterator still points to [2, 3], cache is empty

Operation 5: next()

• Since has_peeked = False, directly call iterator.next()
• This returns 2 and advances the iterator
• Return 2
• State: iterator points to [3], cache is still empty

Operation 6: peek()

• Since has_peeked = False, call iterator.next() which returns 3
• Cache it: peeked_element = 3, has_peeked = True
• Return 3
• State: iterator is now empty [], but we have 3 cached

Operation 7: hasNext()

• Check: has_peeked = True, so return True
• (The underlying iterator is empty, but we have a cached element)

Operation 8: next()

• Since has_peeked = True, return cached peeked_element = 3
• Clear cache: has_peeked = False, peeked_element = None
• Return 3
• State: iterator is empty [], cache is empty

Operation 9: hasNext()

• Check: has_peeked = False and iterator.hasNext() = False
• Return False (no more elements)

This walkthrough demonstrates how the caching mechanism allows us to "look ahead" without losing elements, maintaining the correct iterator behavior throughout.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(): O(1) - Simply initializes instance variables without any loops or recursive calls.
• peek(): O(1) - Either returns the already peeked element or calls iterator.next() once and stores it. Both operations are constant time.
• next(): O(1) - Either returns the peeked element or calls iterator.next() once. Both operations are constant time.
• hasNext(): O(1) - Performs a simple boolean check and calls iterator.hasNext() which is assumed to be O(1).

Overall, all operations of the PeekingIterator have O(1) time complexity.

Space Complexity:

• O(1) - The implementation uses only two additional instance variables: has_peeked (a boolean) and peeked_element (stores at most one element from the iterator). The space usage doesn't scale with the input size, making it constant space complexity.

The solution efficiently implements a peeking iterator by caching at most one element when peek() is called, allowing subsequent peek() calls to return the same element without advancing the underlying iterator. This design maintains optimal time and space complexity for all operations.

Common Pitfalls

1. Not Handling Empty Iterator in peek()

A critical pitfall is calling peek() when the iterator has no more elements. The current implementation will call self.iterator.next() which could raise an exception or return undefined behavior on an empty iterator.

Problem Example:

iter = PeekingIterator(Iterator([]))  # Empty iterator
val = iter.peek()  # This will crash or throw an exception!

Solution: Add a check before calling the underlying iterator's next():

def peek(self) -> int:
    if not self.has_peeked:
        if not self.iterator.hasNext():
            raise StopIteration("No more elements to peek")
        self.peeked_element = self.iterator.next()
        self.has_peeked = True
    return self.peeked_element

2. Thread Safety Issues

In multi-threaded environments, the caching mechanism isn't thread-safe. If multiple threads access the same PeekingIterator instance, race conditions can occur between checking has_peeked and modifying it.

Problem Scenario:

• Thread A calls peek() and sets has_peeked = True
• Thread B calls next() simultaneously and resets has_peeked = False
• This leads to inconsistent state and incorrect behavior

Solution: Use thread synchronization:

import threading

class PeekingIterator:
    def __init__(self, iterator: Iterator):
        self.iterator = iterator
        self.has_peeked = False
        self.peeked_element = None
        self.lock = threading.Lock()
  
    def peek(self) -> int:
        with self.lock:
            if not self.has_peeked:
                self.peeked_element = self.iterator.next()
                self.has_peeked = True
            return self.peeked_element
  
    def next(self) -> int:
        with self.lock:
            if not self.has_peeked:
                return self.iterator.next()
            result = self.peeked_element
            self.has_peeked = False
            self.peeked_element = None
            return result

3. Forgetting to Reset Cache State

A subtle bug can occur if you forget to properly reset both has_peeked and peeked_element in the next() method. Setting only one but not the other can lead to memory leaks or incorrect values being returned.

Incorrect Implementation:

def next(self):
    if not self.has_peeked:
        return self.iterator.next()
    result = self.peeked_element
    self.has_peeked = False
    # Forgot to set self.peeked_element = None
    return result

This keeps a reference to the old element unnecessarily, which could be problematic for large objects.

4. Incorrect hasNext() Logic with Short-Circuit Evaluation

The order of conditions in hasNext() matters for efficiency. The current implementation correctly checks self.has_peeked first (which is O(1)) before calling self.iterator.hasNext() (which might be more expensive).

Less Efficient (but still correct):

def hasNext(self) -> bool:
    return self.iterator.hasNext() or self.has_peeked  # Calls hasNext() unnecessarily

The current implementation leverages short-circuit evaluation properly - if self.has_peeked is True, it doesn't need to check the underlying iterator at all.