Peeking Iterator | February LeetCoding Challenge 2021 | Day 8
logo
Manas Sinha
Developer | Designer

By Manas | 8 February 2021

February LeetCoding Challenge 2021

Day 8

PEEKING ITERATOR

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 1
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.
Follow up: How would you extend your design to be generic and work with all types, not just integer?
Think of “looking ahead”. You want to cache the next element.
Is one variable sufficient? Why or why not?
Test your design with call order of peek() before next() vs next() before peek().
For a clean implementation, check out Google’s guava library source code.

Explanation

Maintain two variables. One is the peeking iterator and another a boolean that keep tracks that if there is a next value. We are not using the hasNext() function of the Iterator class directly in the peekingIterator’s hasNext() function because at any moment of time our peeking iterator is one step in the future,i.e.,at the next element that has to be returned. so for an array like [1,2,3] if our iterator is at '3' the hasNext() function of Iterator class will return false but we need to return true since there is still the last element left.
ALGORITHM:
  • Declare two variables, int peek_data; boolean has_next
  • return the peek_data if peek() is called.
  • if next() is called, store the peek_data is a temp variable and advance the peek_data one step forward. Also update the has_next.
  • return has_next if hasNext() is called

code

class PeekingIterator : public Iterator {
public:
    int peek_data;
    bool has_next;
	PeekingIterator(const vector<int>& nums) : Iterator(nums) {
	    // Initialize any member here.
	    // **DO NOT** save a copy of nums and manipulate it directly.
	    // You should only use the Iterator interface methods.
        has_next = Iterator::hasNext();
        if(has_next) peek_data = Iterator::next();
        
	    
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	int peek() {
        return peek_data;
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	int next() {
	    int res = peek_data;    
        has_next = Iterator::hasNext();
        if(has_next) peek_data = Iterator::next();
        
        return res;
	}
	
	bool hasNext() const {
	    return has_next;
    }
};

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply