Peeking Iterator

#26 Most AskedMedium

Peeking Iterator #26 Most Asked

Medium

14 views

Topics:

ArraysTwo Pointers

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?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the elements returned by the iterator's `next()` method? Can it be any type, or is it restricted to integers?
Is it possible for the underlying iterator to be empty initially, or to become empty after several calls to `next()`?
Should the `peek()` method throw an exception or return a specific value (like null) if the iterator is empty (i.e., `hasNext()` returns false)?
How many times will `peek()` be called in relation to `next()` and `hasNext()`? Should I optimize for frequent peeking versus infrequent peeking?
Is the original iterator guaranteed to be well-behaved, meaning that `hasNext()` and `next()` will function correctly according to the iterator contract (i.e., `next()` is only called when `hasNext()` returns true)?

Brute Force Solution

Approach

We want to build a special tool that lets us look at the next item in a sequence without actually moving to it. The brute force method simulates this by keeping track of all the items and manually peeking and advancing through them whenever asked.

Here's how the algorithm would work step-by-step:

Keep a copy of the entire sequence of items we're working with.
When someone asks to 'peek', simply look at the first item in our copied sequence, but don't remove it.
When someone asks to 'next', return the first item in our copied sequence and then remove it from the copied sequence.
When someone asks 'has next', simply check if our copied sequence is empty or not. If it's not empty, then there is a next item.

Code Implementation

class PeekingIterator:
    def __init__(self, iterator):
        # Create a list to hold the iterator's elements.
        self.all_elements = list(iterator)
        
        self.current_index = 0

    def peek(self):
        # Check if there are any more elements.
        if self.has_next():

            # Return the element at the current index without advancing.
            return self.all_elements[self.current_index]
        else:
            return None

    def next(self):
        # Check if there are any more elements.
        if self.has_next():

            # Retrieve the element at the current index and advance the index.
            next_element = self.all_elements[self.current_index]
            self.current_index += 1
            return next_element
        else:
            return None

    def has_next(self):
        # Check if the current index is within the bounds of all_elements.
        return self.current_index < len(self.all_elements)

Big(O) Analysis

Time Complexity

O(n) – The constructor copies the entire iterator into a list, which takes O(n) time, where n is the number of elements in the iterator. The peek, next, and hasNext methods operate on the copied list. peek simply accesses the first element (O(1)), next removes the first element (O(n) in the worst case because other elements need to be shifted), and hasNext checks the size of the list (O(1)). Since next can take O(n) time in the worst case, across a series of n calls to next, we could end up with O(n*n) in total, but for any single next call, we perform O(n) actions. Since the construction also copies every element (O(n)), the dominant operation is the copying in the constructor; however, worst case operations are of O(n) overall if next is invoked repeatedly. Therefore, we select O(n) as the overall runtime.

Space Complexity

O(N) – The brute force approach described creates a copy of the entire input sequence of items. This copied sequence, acting as a temporary list, stores all N elements from the original sequence. Therefore, the auxiliary space used scales linearly with the number of items in the input. This leads to a space complexity of O(N).

Optimal Solution

Approach

The Peeking Iterator problem asks us to extend the functionality of a regular iterator. The trick is to store the 'next' element that the iterator would return, so we can 'peek' at it without actually consuming it. We use this stored value strategically to avoid repetitive calls to the underlying iterator.

Here's how the algorithm would work step-by-step:

When the iterator is initialized, immediately try to get the first element from the original iterator and store it in a special variable.
The 'peek' operation simply returns the stored element, without changing anything. It's like looking at a preview.
The 'next' operation returns the stored element, and then tries to fetch the next element from the original iterator to replace the stored element. If there are no more elements, the stored element is set to a special value indicating the end.
The 'hasNext' operation checks if there is a stored element. If there is, it means there are more elements to iterate through. If not, it means we've reached the end.

Code Implementation

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

        # Initialize the next element during instantiation.
        if iterator.hasNext():
            self.next_element = iterator.next()

    def peek(self):
        return self.next_element

    def next(self):
        element_to_return = self.next_element

        # Advance the stored element.
        if self.iterator.hasNext():
            self.next_element = self.iterator.next()

        # Set next element to None if iterator is exhausted.
        else:
            self.next_element = None

        return element_to_return

    def hasNext(self):
        # True if there is a stored next element.
        return self.next_element is not None

Big(O) Analysis

Time Complexity

O(1) – The PeekingIterator's methods (peek, next, hasNext) all perform a constant amount of work. Initialization might call the underlying iterator's next once, but that's a fixed cost per iterator creation. Subsequent calls to peek, next, and hasNext involve only checking a cached value or performing a simple assignment, independent of the size of the iterated collection (n). Therefore, each operation takes constant time, resulting in O(1) time complexity for each method.

Space Complexity

O(1) – The Peeking Iterator implementation stores a single variable to hold the 'next' element obtained from the underlying iterator. Regardless of the number of elements N in the original iterator, only one element is stored at any given time. Therefore, the auxiliary space used is constant. This results in a space complexity of O(1).

Edge Cases

Case	How to Handle
Iterator is initially empty.	peek() should return null or throw an exception, next() should throw an exception or return null, hasNext() should return false.
Iterator contains only one element.	peek() should return that element, next() should return that element, hasNext() should return false after the first next().
Calling peek() multiple times in a row.	Subsequent calls to peek() without calling next() should return the same element.
Calling next() after calling peek().	The next() call should return the element that was previously peeked.
Calling next() when hasNext() returns false.	next() should return null or throw an exception to signal the end of the iteration.
Integer overflow if the iterator returns large numbers	The peeking iterator should be able to store and return large integers without causing an overflow, potentially requiring long data types
Large number of peek() calls without calling next().	The solution should handle a large number of consecutive peek() calls without significant performance degradation, storing the peeked value efficiently.
Underlying iterator throws exceptions	The PeekingIterator's methods should gracefully handle exceptions thrown by the underlying iterator's next() or hasNext() methods.

Iterator is initially empty.

How to Handle:

peek() should return null or throw an exception, next() should throw an exception or return null, hasNext() should return false.

Iterator contains only one element.

How to Handle:

peek() should return that element, next() should return that element, hasNext() should return false after the first next().

Calling peek() multiple times in a row.

How to Handle:

Subsequent calls to peek() without calling next() should return the same element.

Calling next() after calling peek().

How to Handle:

The next() call should return the element that was previously peeked.

Calling next() when hasNext() returns false.

How to Handle:

next() should return null or throw an exception to signal the end of the iteration.

Integer overflow if the iterator returns large numbers

How to Handle:

The peeking iterator should be able to store and return large integers without causing an overflow, potentially requiring long data types

Large number of peek() calls without calling next().

How to Handle:

The solution should handle a large number of consecutive peek() calls without significant performance degradation, storing the peeked value efficiently.

Underlying iterator throws exceptions

How to Handle:

The PeekingIterator's methods should gracefully handle exceptions thrown by the underlying iterator's next() or hasNext() methods.