284. Peeking Iterator

MediumDesignArrayIterator
Leetcode Link

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1class Iterator:
2    # A class that represents an iterator.
3    def __init__(self, nums):
4        """
5        Initialize the iterator object to the beginning of a list.
6
7        :param nums: A list of integers.
8        """
9        # Your Iterator class here.
10
11    def has_next(self):
12        """
13        Checks if the iteration has more elements.
14
15        :return: True if there are more elements, False otherwise.
16        """
17        # Your has_next logic here.
18
19    def next(self):
20        """
21        Returns the next element in the iteration.
22
23        :return: The next integer in the iteration.
24        """
25        # Your next logic here.
26
27
28class PeekingIterator:
29    def __init__(self, iterator):
30        """
31        Initialize a PeekingIterator with an iterator.
32
33        :param iterator: An instance of the Iterator class.
34        """
35        self.iterator = iterator
36        self.peeked_element = None  # The element that has been peeked at.
37        self.has_peeked = False     # Flag to check if we have a peeked element.
38
39    def peek(self):
40        """
41        Returns the next element in the iteration without advancing the iterator.
42
43        :return: The next integer in the iteration.
44        """
45        if not self.has_peeked:
46            # If we haven't peeked yet, retrieve the next element
47            self.peeked_element = self.iterator.next()
48            self.has_peeked = True  # Set the flag to indicate that we have peeked
49        return self.peeked_element
50
51    def next(self):
52        """
53        Returns the next element and advances the iterator.
54
55        :return: The next integer in the iteration.
56        """
57        if not self.has_peeked:
58            # If we haven't peeked, we simply get the next element from the iterator
59            return self.iterator.next()
60      
61        # If we have peeked, we return the peeked element and reset the peeked state
62        result = self.peeked_element
63        self.peeked_element = None
64        self.has_peeked = False
65        return result
66
67    def has_next(self):
68        """
69        Checks if there are more elements in the iteration.
70
71        :return: True if there are more elements, False otherwise.
72        """
73        # We have an element if we already peeked or if the iterator has more elements
74        return self.has_peeked or self.iterator.has_next()
75
76
77# Usage example
78# iter = PeekingIterator(Iterator(nums))
79# while iter.has_next():
80#     val = iter.peek()   # View the next element but do not advance the iterator.
81#     iter.next()         # Should return the same value as [val].
82
1import java.util.Iterator;
2
3// The PeekingIterator class wraps a standard Iterator and allows for peeking ahead at the next element without advancing the iterator.
4public class PeekingIterator implements Iterator<Integer> {
5    private Iterator<Integer> iterator; // An iterator over a collection of Integers
6    private boolean hasPeeked; // A flag indicating if we've already peeked at the next element
7    private Integer peekedElement; // The next element, if we've peeked
8
9    // Constructor initializes the PeekingIterator using an existing Iterator.
10    public PeekingIterator(Iterator<Integer> iterator) {
11        this.iterator = iterator;
12    }
13
14    // The peek method returns the next element in the iteration without advancing the iterator.
15    public Integer peek() {
16        if (!hasPeeked) {
17            if (iterator.hasNext()) {
18                peekedElement = iterator.next(); // Store the next element so we can return it later
19            } else {
20                throw new NoSuchElementException(); // In case there are no more elements to peek
21            }
22            hasPeeked = true;
23        }
24        return peekedElement;
25    }
26
27    // The next method should behave the same as if using the Iterator directly.
28    @Override
29    public Integer next() {
30        if (!hasPeeked) {
31            return iterator.next(); // Directly return the next element from the iterator
32        }
33        Integer result = peekedElement; // Return the stored peeked element
34        hasPeeked = false; // Reset the peeked flag
35        peekedElement = null; // Clear the stored element
36        return result;
37    }
38
39    // The hasNext method indicates whether the iteration has more elements.
40    @Override
41    public boolean hasNext() {
42        return hasPeeked || iterator.hasNext(); // Return true if we've peeked or if the iterator has more elements
43    }
44}
45
1class PeekingIterator : public Iterator {
2private:
3    bool hasPeeked;           // Flag to check if we already peeked at the next element
4    int peekedValue;          // Stores the value of the peeked element if hasPeeked is true
5  
6public:
7    PeekingIterator(const vector<int>& nums)
8        : Iterator(nums), hasPeeked(false)
9    {
10        // Constructor inherits from the Iterator and initializes hasPeeked flag to false.
11        // Note that initialization of hasPeeked is done above in the member initializer list.
12    }
13
14    // Peek method allows us to see what the next element in the iterator is without advancing the iterator.
15    int peek() {
16        if (!hasPeeked) {
17            // If we haven't already peeked, fetch the next element and set the hasPeeked flag
18            peekedValue = Iterator::next();  // Get the next element from the iterator
19            hasPeeked = true;               // Set the peek flag
20        }
21        return peekedValue; // Return the peeked value
22    }
23
24    // Override the next() method to consider if we have already peeked at the next element.
25    int next() {
26        if (!hasPeeked) {
27            // If we haven't peeked, return the next element from the iterator directly
28            return Iterator::next();
29        }
30        // If there is a peeked value, reset the hasPeeked flag since next() consumes the peeked element
31        hasPeeked = false;
32        return peekedValue;  // Return the peeked value which is the next element
33    }
34
35    // Override the hasNext() method to consider the peek scenario.
36    bool hasNext() const {
37        // If either we have a peeked element or if the underlying iterator has a next element,
38        // we have a next element
39        return hasPeeked || Iterator::hasNext();
40    }
41};
42
1let hasPeeked: boolean = false;            // Flag to check if we already peeked at the next element
2let peekedValue: number;                   // Stores the value of the peeked element if hasPeeked is true
3let iterator: Iterator<number>;            // The iterator instance which is adapted by the PeekingIterator functionality
4
5function PeekingIterator(nums: number[]) {
6    // Initialize the iterator with nums.
7    iterator = nums[Symbol.iterator]();
8}
9
10function peek(): number {
11    if (!hasPeeked) {
12        // If we haven't already peeked, fetch the next element and set the hasPeeked flag
13        const result = iterator.next();
14        if (!result.done) {
15            peekedValue = result.value;
16            hasPeeked = true;               // Set the peek flag
17        }
18    }
19    return peekedValue; // Return the peeked value
20}
21
22function next(): number {
23    if (!hasPeeked) {
24        // If we haven't peeked, extract the next element from the iterator directly and return it
25        const result = iterator.next();
26        if (!result.done) {
27            return result.value;
28        }
29    } else {
30        // If there is a peeked value, reset the hasPeeked flag since next() consumes the peeked element
31        hasPeeked = false;
32        return peekedValue;  // Return the peeked value which is the next element
33    }
34}
35
36function hasNext(): boolean {
37    // If there is a peeked element or if the underlying iterator has a next element, we have a next element
38    return hasPeeked || !iterator.next().done;
39}
40

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More