Leetcode 284. Peeking Iterator

Problem Explanation

The problem asks us to add extra functionality to an iterator interface. This interface already contains next() and hasNext() methods, now we have to implement a peek() method for it.

The peek() method shows us the next number that method next() will return when called.

To add clarity, let's consider an example - if we're given a list [1,2,3]:

1. If we call next(), it will return the first number, which is 1.

2. Then, we call peek(), it will return the next number 2, but the state of iterator doesn't change. It's a way to view the next item without shifting our current position in the number sequence.

3. Call next() after the peek(), it will return 2 because that was our next item.

4. Now call next() for one final time, and it will return 3, the last element.

5. At this point, the list has been traversed completely, so if we call hasNext(), it should return false.

In the follow-up question, we're asked to modify our design to apply to all types, not just integer values.

Solution Approach

The solution to this problem can be found by maintaining a copy of the current iterator. When we initialize PeekingIterator, we make a copy of the current iterator. In the peek() method, we use the copy to view the next item, and thus our state in the original iterator does not change until we call the next() method.

Python Solution

1
2python
3class PeekingIterator:
4    def __init__(self, iterator):
5        self.iterator = iterator
6        self._next = next(self.iterator)
7
8    def peek(self):
9        return self._next
10
11    def next(self):
12        if self._next is None:
13            raise StopIteration()
14        to_return = self._next
15        self._next = next(self.iterator, None)
16        return to_return
17
18    def hasNext(self):
19        return self._next is not None

Java Solution

1
2java
3public class PeekingIterator implements Iterator<Integer> {
4    
5   private Iterator<Integer> iterator;
6   private Integer next;
7    
8   public PeekingIterator(Iterator<Integer> iterator) {
9    // initialize any member here.
10    this.iterator = iterator;
11    if (iterator.hasNext()) {
12        next = iterator.next();
13    }
14   }
15
16    // Returns the next element in the iteration without advancing the iterator.
17    public Integer peek() {
18        return next;
19    }
20
21    // hasNext() and next() should behave the same as in the Iterator interface.
22    @Override
23    public Integer next() {
24        Integer toReturn = next;
25        next = iterator.hasNext() ? iterator.next(): null;
26        return toReturn;
27    }
28
29   @Override
30   public boolean hasNext() {
31       return next != null;
32   }
33}

JavaScript Solution

1
2javascript
3class PeekingIterator {
4  constructor(iter) {
5    this.iter = iter;
6    this.peeked = this.iter[Symbol.iterator]().next();
7  }
8
9  peek(){
10    return this.peeked.value;
11  }
12
13  next() {
14   let value = this.peeked.value;
15   this.peeked = this.iter[Symbol.iterator]().next();
16   return value;
17  }
18
19  hasNext() {
20    return !this.peeked.done;
21  }
22}

C++ Solution

1
2cpp
3class PeekingIterator : public Iterator {
4public:
5    PeekingIterator(const vector<int>& nums) : Iterator(nums) {}
6
7    // Returns the next element in the iteration without advancing the iterator.
8    int peek() {
9        return Iterator(*this).next();
10    }
11
12    // hasNext() and next() should behave the same as in the Iterator interface.
13    // Override them if needed.
14    int next() {
15        return Iterator::next();
16    }
17
18    bool hasNext() const {
19        return Iterator::hasNext();
20    }
21};

C# Solution

1
2csharp
3public class PeekingIterator {
4    private int? cachedNext;
5    private IEnumerator<int> iter;
6
7    public PeekingIterator(IEnumerator<int> iterator) {
8        // Initialize any member here.
9        iter = iterator;
10        if(iter.MoveNext()){
11            cachedNext = iter.Current;
12        }
13    }
14
15    // Returns the next element in the iteration without advancing the iterator.
16    public int Peek() {
17        return cachedNext.Value;
18    }
19
20    // Returns the next element in the iteration and advances the iterator.
21    public int Next() {
22        int toReturn = cachedNext.Value;
23        cachedNext = null;
24        if (iter.MoveNext()) cachedNext = iter.Current;
25        return toReturn;
26    }
27
28    // Returns false if the iterator is refering to the end of the array of true otherwise.
29    public bool HasNext() {
30       return cachedNext.HasValue;
31    }
32}

These solutions work by storing the next value from the iterator during initialization, and then each time peek() or next() is called, update this stored value. When next() is called, it returns the stored value, and peek() simply returns it without moving on to the next value. Finally, hasNext() checks if this stored value is null or not.To add various types of users, we need to design a generic interface or class that iterates over a list of elements. This class should work for any type of data.

Generic Class Solution

For different types of data, we will create a universal class. This class will encapsulate all data types and have functions like next(), hasNext(), and peek() as in the examples above. Here is how you can create a universal class in Python and Java:

Python

1
2python
3class PeekingIterator:
4    def __init__(self, iterator):
5        self.iterator = iter(iterator)
6        try:
7            self.next_element = next(self.iterator)
8        except StopIteration:
9            self.next_element = None
10
11    def peek(self):
12        return self.next_element
13
14    def next(self):
15        if self.next_element is None:
16            raise StopIteration()
17        to_return = self.next_element
18        try:
19            self.next_element = next(self.iterator)
20        except StopIteration:
21            self.next_element = None
22        return to_return
23
24    def hasNext(self):
25        return self.next_element is not None

Java

1
2java
3class PeekingIterator<E> implements Iterator<E> {
4    private Iterator<E> iter;
5    private E next;
6    
7    public PeekingIterator(Iterator<E> iterator) {
8        this.iter = iterator;
9        if (iter.hasNext()) {
10            next = iter.next();
11        }
12    }
13    
14    public E peek() {
15        return next;
16    }
17    
18    public E next() {
19        E toReturn = next;
20        next = iter.hasNext() ? iter.next(): null;
21        return toReturn;
22    }
23    
24    public boolean hasNext() {
25        return next != null;
26    }
27}

In conclusion, the main idea to solve this problem is to store an extra variable to keep track of the "peeked at" element. Therefore, you can call the peek() method and get the next element without advancing the original iterator. When the next() method is called, you advance the iterator and update the "peeked at" element. The hasNext() method checks if we still have elements to traverse in the list. The solution can be easily extended to work for all data types.