Peeking Iterator

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.

Problem#

Examples#

Solution#

Method 1 - Implementing iterator#

Code#

Complexity#