Peeking Iterator - Leetcode Solution

Problem Statement

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation — it essentially peek() at the element that will be returned by the next call to next().

Example:

Assume that the iterator is initialized to the beginning of the list: [1,2,3,4].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element.

Call next() again gets you 2, because peek() returned the second element.

You call next() the final time and get 3, the third element.

You then call hasNext() and it returns false.

Solution

The problem can be solved by using a boolean variable to keep track of whether the next element has been peeked or not. If the next element has been peeked, then it should not be fetched again. If the next element has not been peeked, it can be fetched by calling the original iterator’s next() method.

Algorithm

1. Initialize variables: boolean peeked = false, int nextElement = 0.
2. Implement the hasNext() method as follows: a. If the peeked variable is true, return true. b. Otherwise, call the original iterator’s hasNext() method to check if there are any more elements left to retrieve.
3. Implement the next() method as follows: a. If the peeked variable is true, set peeked = false and return the nextElement variable. b. If the peeked variable is false, call the original iterator’s next() method and return the retrieved element.
4. Implement the peek() method as follows: a. If the peeked variable is false, call the original iterator’s next() method to retrieve the next element. b. Set peeked = true and nextElement = the retrieved element. c. Return the nextElement variable.

Implementation

class PeekingIterator implements Iterator<Integer> { Iterator<Integer> iterator; Integer nextElement; boolean peeked;

public PeekingIterator(Iterator<Integer> iterator) {
    this.iterator = iterator;
    peeked = false;    
}

public Integer peek() {
    if(!peeked) {
        nextElement = iterator.next();
        peeked = true;
    }
    return nextElement;
}

@Override
public Integer next() {
    if(peeked) {
        peeked = false;
        return nextElement;
    }
    return iterator.next();
}

@Override
public boolean hasNext() {
    if(peeked)
        return true;
    return iterator.hasNext();
}

}

Time Complexity: The time complexity of the peek(), hasNext(), and next() methods is O(1), as they perform constant time operations.

Space Complexity: The space complexity of the PeekingIterator class is O(1), as it only uses a constant amount of extra space to store the variables.

1