{x}
blog image

Peeking Iterator

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?

Solution Explanation

This problem requires designing a PeekingIterator class that extends the functionality of a standard iterator by adding a peek() method. The peek() method allows retrieving the next element without advancing the iterator. The solution involves storing a peeked element and a boolean flag to track whether an element has been peeked.

Approach

The core idea is to maintain an additional variable to store the "peeked" element and a boolean flag to indicate whether a peek operation has already been performed.

  1. Constructor: The constructor initializes the PeekingIterator with the given iterator. It also initializes a has_peeked flag to False and peeked_element to None.

  2. peek() method: If has_peeked is False, it calls the iterator's next() method to get the next element, stores it in peeked_element, and sets has_peeked to True. Then it returns the peeked_element.

  3. next() method: If has_peeked is True, it means a peek operation was performed earlier. It returns the peeked_element, resets has_peeked to False, and sets peeked_element back to None. Otherwise, it directly calls the iterator's next() method and returns the result.

  4. hasNext() method: This method checks if either has_peeked is True (meaning there's a peeked element) or the iterator has more elements using its hasNext() method.

Code Explanation (Python3)

class PeekingIterator:
    def __init__(self, iterator):
        self.iterator = iterator
        self.has_peeked = False
        self.peeked_element = None
 
    def peek(self):
        if not self.has_peeked:
            self.peeked_element = self.iterator.next()
            self.has_peeked = True
        return self.peeked_element
 
    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
 
    def hasNext(self):
        return self.has_peeked or self.iterator.hasNext()

The code in other languages (Java, C++, Go) follows the same logic, adapting the syntax and data structures to the respective languages.

Time and Space Complexity

  • Time Complexity:

    • __init__: O(1) - Constant time initialization.
    • peek(): O(1) - Constant time peek operation (at most one call to next()).
    • next(): O(1) - Constant time to return the next element.
    • hasNext(): O(1) - Constant time to check for next element.

  • Space Complexity: O(1) - Constant extra space is used to store has_peeked and peeked_element. The space usage doesn't depend on the input size.

The solution efficiently provides the peeking functionality without significantly impacting the time or space complexity of the original iterator.