DEV Community

loading...
Cover image for Solution: Peeking Iterator

Solution: Peeking Iterator

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・3 min read

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


Leetcode Problem #284 (Medium): Peeking Iterator


Description:

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().


Examples:

Example:
Input: ["PeekingIterator","next","peek","next","next","hasNext"]
[[[1,2,3]],[],[],[],[],[]]
Output: [null,1,2,2,3,false]
Explanation Assume that the iterator is initialized to the beginning of the list: [1,2,3].

Call next() gets you 1, the first element in the list.
Now you call peek() and it returns 2, the next element.
Calling next() after that still return 2.
You call next() the final time and it returns 3, the last element.
Calling hasNext() after that should return false.

Idea:

The trick here is realizing that you're not building the class from scratch. Instead, you're building a class that is constructed from another class instance.

Our new class will do the same things that the original class does, except that it will store the next value separately, so that we can peek at it without it being removed. The only challenging thing at this point is to make sure that the next function checks to make sure if there actually is a next element before updating the stored value.


Javascript Code:

The best result for the code below is 72ms / 39.0MB (beats 93% / 83%).

class PeekingIterator {
    constructor(iterator) {
        this.iterator = iterator
        this.nextVal = this.iterator.hasNext() ? this.iterator.next() : null
    };

    peek() {
        return this.nextVal
    };

    next() {
        let nextVal = this.nextVal
        this.nextVal = this.iterator.hasNext() ? this.iterator.next() : null
        return nextVal
    };

    hasNext() {
        return !!this.nextVal
    };
};
Enter fullscreen mode Exit fullscreen mode

Python Code:

The best result for the code below is 20ms / 14.2MB (beats 99% / 100%).

class PeekingIterator:
    def __init__(self, iterator):
        self.iterator = iterator
        self.nextVal = self.iterator.next() if self.iterator.hasNext() else None

    def peek(self):
        return self.nextVal

    def next(self):
        nextVal = self.nextVal
        self.nextVal = self.iterator.next() if self.iterator.hasNext() else None
        return nextVal

    def hasNext(self):
        return bool(self.nextVal)
Enter fullscreen mode Exit fullscreen mode

Java Code:

The best result for the code below is 4ms / 38.6MB (beats 94% / 96%).

class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iter;
    Integer nextVal;

    public PeekingIterator(Iterator<Integer> iterator) {
        iter = iterator;
        nextVal = iter.hasNext() ? iter.next() : null;
    }

    public Integer peek() {
        return nextVal;
    }

    @Override
    public Integer next() {
        Integer oldNext = nextVal;
        nextVal = iter.hasNext() ? iter.next() : null;
        return oldNext; 
    }

    @Override
    public boolean hasNext() {
        return (nextVal != null);
    }
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:

The best result for the code below is 0ms / 7.3MB (beats 100% / 94%).

class PeekingIterator : public Iterator {
public:
    int nextVal;

    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        nextVal = Iterator::hasNext() ? Iterator::next() : NULL;
    }

    int peek() {
        return nextVal;
    }

    int next() {
        int oldNext = nextVal;
        nextVal = Iterator::hasNext() ? Iterator::next() : NULL;
        return oldNext; 
    }

    bool hasNext() const {
        return (nextVal != NULL);
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)