Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

Solution

Method 1 - Implementing iterator

Here is the approach:

  • The PeekingIterator class wraps around an Iterator<Integer> and adds the peek functionality.
  • The peek method simply returns the cached nextElement.
  • The next method returns the cached nextElement and updates it by fetching the next element from the iterator.
  • The hasNext method checks if the nextElement is not null.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class PeekingIterator implements Iterator<Integer> {
    private Integer nextElement;
    private Iterator<Integer> iterator;

    public PeekingIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
        if (iterator.hasNext()) {
            nextElement = iterator.next();
        }
    }

    public Integer peek() {
        return nextElement;
    }

    @Override
    public Integer next() {
        Integer result = nextElement;
        nextElement = iterator.hasNext() ? iterator.next() : null;
        return result;
    }

    @Override
    public boolean hasNext() {
        return nextElement != null;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

    def peek(self):
        if self._peeked is None:
            if self.iterator.hasNext():
                self._peeked = self.iterator.next()
        return self._peeked

    def next(self):
        if self._peeked is not None:
            next_element = self._peeked
            self._peeked = None
        else:
            next_element = self.iterator.next()
        return next_element

    def hasNext(self):
        return self._peeked is not None or self.iterator.hasNext()

# Example Iterator class for testing
class Iterator:
    def __init__(self, nums):
        self.nums = nums
        self.index = 0

    def next(self):
        result = self.nums[self.index]
        self.index += 1
        return result

    def hasNext(self):
        return self.index < len(self.nums)

Complexity

  • ⏰ Time complexity: O(1) for all operations (peek, next, and hasNext) as we perform constant-time operations.
  • 🧺 Space complexity: O(1) as we only use a few extra variables to store the current element and the iterator.