284. Peeking Iterator

Description

The PeekingIterator class allows you to peek at the next element in an iterator without advancing the iterator. This is useful in scenarios where you need to look ahead at the next element without consuming it. The class implements the basic operations: peek(), next(), and hasNext().

• peek(): Returns the next element without advancing the iterator.
• next(): Returns the next element and advances the iterator.
• hasNext(): Returns whether the iterator has more elements.

Intuition

The problem revolves around managing the state of the iterator such that we can look ahead at the next element without actually moving the iterator forward. The main challenge is to ensure that if we peek at an element, we can still retrieve it later with next() without losing any elements or advancing the iterator prematurely.

Approach

1. Internal State: - Use an internal variable pk to store the value of the next element when peek() is called. This prevents the iterator from advancing prematurely. - Use a boolean flag (or a null check) to track whether the peeked value is currently stored.
2. peek() Method: - If there is no stored peek value (pk is null or None), retrieve the next element from the iterator and store it. - Return the stored value.
3. next() Method: - If there is a stored peek value, return it and reset the stored value to null or None. - If there is no stored peek value, simply return the next element from the iterator.
4. hasNext() Method: - Check if there is a stored peek value or if the iterator has more elements.

Complexity

Time Complexity:

• peek(), next(), and hasNext() all run in O(1) time since they involve simple checks or retrievals from the iterator.

Space Complexity:

• O(1) because only a constant amount of extra space is used to store the peeked value.

Code

C++

class PeekingIterator : public Iterator {
private:
    Iterator* it;
    int pk;
    bool hasPeeked;

public:
    PeekingIterator(const vector& nums) : Iterator(nums) {
        it = this;
        hasPeeked = false;
    }
    
    int peek() {
        if (!hasPeeked) {
            pk = it->next();
            hasPeeked = true;
        }
        return pk;
    }
    
    int next() {
        if (!hasPeeked) {
            return it->next();
        }
        int ret = pk;
        hasPeeked = false;
        return ret;
    }
    
    bool hasNext() const {
        return hasPeeked || it->hasNext();
    }
};

Python

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

    def peek(self):
        if self.pk is None:
            self.pk = self.it.next()
        return self.pk

    def next(self):
        if self.pk is None:
            return self.it.next()
        ret = self.pk
        self.pk = None
        return ret

    def hasNext(self):
        return self.pk is not None or self.it.hasNext()

Java

class PeekingIterator implements Iterator {
    private Iterator it;
    private Integer pk;

    public PeekingIterator(Iterator iterator) {
        this.it = iterator;
        this.pk = null;
    }
    
    public Integer peek() {
        if (pk == null) {
            pk = it.next();
        }
        return pk;
    }
    
    @Override
    public Integer next() {
        if (pk == null) {
            return it.next();
        }
        Integer ret = pk;
        pk = null;
        return ret;
    }
    
    @Override
    public boolean hasNext() {
        return pk != null || it.hasNext();
    }
}

JavaScript

/**
 * @param {Iterator} iterator
 */
class PeekingIterator {
constructor(iterator) {
this.it = iterator;
this.pk = null;
}
peek() {
if (!this.pk) this.pk = this.it.next();
return this.pk;
}
next() {
if(!this.pk) return this.it.next();
let t = this.pk;
this.pk = null;
return t;
}
hasNext() {
if(!this.pk) return this.it.hasNext();
return true;
}
}

/** 
 * Your PeekingIterator object will be instantiated and called as such:
 * var obj = new PeekingIterator(arr)
 * var param_1 = obj.peek()
 * var param_2 = obj.next()
 * var param_3 = obj.hasNext()
 */