Problem Description

The task is to design a PeekingIterator that extends the functionality of a standard iterator. Unlike a regular iterator that only supports next and hasNext operations, the PeekingIterator should also support a peek operation. The peek method allows the user to look at the next element the iterator would return without actually moving the iterator forward. This can be particularly useful when you need to make decisions based on the next item without actually removing it from the iteration sequence.

Intuition

The intuitive approach to solving this problem involves caching the next element of the iterator after a peek call, because a regular iterator would not allow us to see the next element without advancing to it. Thus, we need an additional state in PeekingIterator to remember whether we’ve peeked at the next element and what that element is.

Here is a step-by-step break-down of the intuition behind the solution:

1. Initialize State: When we create a PeekingIterator, we store the original Iterator and initialize a state indicating whether the iterator has been peeked or not (has_peeked), and a variable to store the peeked value (peeked_element).

2. Peek Operation: For the peek function we check if we have already called a peek without a subsequent next. If we haven’t peeked yet (has_peeked is False), we call next on the underlying iterator and store the value. We then return this stored value without changing the position of the underlying iterator.

3. Next Operation: If a peek has not occurred, the regular next operation of the underlying iterator is used. If we've already peeked (has_peeked is True), we need to return the stored peeked_element and reset our state so the iterator can advance when next is called again.

4. HasNext Operation: For the hasNext method, we simply return True if we are in the peeked state (as we already have a next element), or we defer to the underlying iterator's hasNext method.

The critical part of this solution is to carefully manage the has_peeked and peeked_element variables so as to not lose track of the iterator's state or prematurely advance the underlying iterator.

Solution Approach

The solution involves implementing a wrapper class around the provided iterator to support the additional peek operation. We make use of the object-oriented concept of class to create our own PeekingIterator that maintains some internal state.

Here's a step-by-step walk through the implementation:

1. Initialization: In the constructor (__init__ method), we accept an Iterator as an argument. We then initialize two instance variables:

   • self.has_peeked: A boolean that indicates if we have already peeked at the next element.
   • self.peeked_element: An integer to hold the next element after a peek. These variables are critical to manage the state between successive peek and next calls.

2. Peek: The peek method checks if we have already peeked (self.has_peeked), and if not, it 'peeks' ahead by calling next on the stored iterator, saving this value to self.peeked_element and setting self.has_peeked to True. The value of self.peeked_element is returned.

3. Next: In the next method, we first check if self.has_peeked is True. If it is, we already have a peeked element to return, which we do. We then reset self.has_peeked to False and self.peeked_element to None to reflect that we no longer have a peeked value. If self.has_peeked is False, we directly return the next element from the underlying iterator.

4. HasNext: For hasNext, we return True if either self.has_peeked is True (since we have a peeked element ready) or if the underlying iterator has more elements, as indicated by its hasNext method.

This implementation uses lazy evaluation for the peek operation. The element is not advanced until necessary (i.e., until the next method is called). This strategy minimizes the number of calls to the underlying iterator's next method, as it only advances the iterator when we're certain we need to consume an element. This approach effectively implements a look-ahead buffer with a capacity of one element.

Such an implementation could be useful in scenarios like comparison-based sorting or merging, where you might need to compare the next item without yet removing it from the iterator.

Example Walkthrough

Let's walk through an example to illustrate the solution approach:

Suppose we have an iterator over a collection with elements [1, 2, 3]. When we wrap this iterator with the PeekingIterator, here's how we can interact with it and what happens internally:

1. We instantiate PeekingIterator with our iterator. self.has_peeked is initialized to False, and self.peeked_element is initialized to None.

2. We call peek() method. Since self.has_peeked is False, the next() method is called on the underlying iterator, giving us 1. Now self.peeked_element becomes 1, and self.has_peeked is now True. The peek() method returns 1, but our iterator's position hasn't advanced.

3. We call the next() method. As self.has_peeked is True, it will return self.peeked_element, which is 1. After this, self.has_peeked is set to False and self.peeked_element to None. The underlying iterator's next element is now 2.

4. We call peek() again. The process from step 2 repeats; self.peeked_element is set to 2, self.has_peeked becomes True, and the method returns 2.

5. We call next(). Since self.has_peeked is True, self.peeked_element (which is 2) is returned. Both self.has_peeked and self.peeked_element are reset as before.

6. We call hasNext(). Since self.has_peeked is False, we check with the underlying iterator, which still has an element (which is 3), so hasNext() returns True.

7. We call next() and receive 3, which is the last element of the iterator.

8. Finally, when we call hasNext() again, it returns False because both self.has_peeked is False and the underlying iterator has no further elements.

This example did not include calls to hasNext() prior to next() or peek() calls, but in practice, the hasNext() method can be used anytime to check if there is a next element available before calling next() or peek() to avoid exceptions from reaching the end of the iterator.

Solution Implementation

Time and Space Complexity

Time Complexity:

• PeekingIterator.__init__(self, iterator):

  • This method only performs some basic variable assignments. The time complexity here is O(1), since no loops or significant operations are involved.

• PeekingIterator.peek(self):

  • If we have not peeked yet (self.has_peeked is False), we call self.iterator.next() once. Since the next() operation of the underlying iterator is assumed to be O(1), the overall time complexity for peek() is also O(1). If we already have a peeked element, we just return it, which is again an O(1) operation.

• PeekingIterator.next(self):

  • When we haven't peeked (self.has_peeked is False), the time complexity is O(1) as it directly returns the next element by calling the iterator's next() method. Once we have peeked (self.has_peeked is True), it involves returning the peeked element and resetting has_peeked and peeked_element which is also O(1) time.

• PeekingIterator.hasNext(self):

  • This method checks whether there's a next element by either checking the self.has_peeked attribute or calling the hasNext() method of the underlying iterator, both of these operations have a time complexity of O(1).

Space Complexity:

• Overall space complexity of the PeekingIterator class:
  • The additional space used by the PeekingIterator class consists of two variables: self.has_peeked and self.peeked_element, which take up O(1) space. The underlying iterator (self.iterator) object is not counted towards the space complexity as it is an input to the class. Therefore, the space complexity of the PeekingIterator is O(1) as it uses a constant amount of extra space.

In conclusion, both the operations peek(), next(), and hasNext() in the PeekingIterator class have a time complexity of O(1) and the space complexity of the PeekingIterator class is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.