Peeking Iterator LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple eBay Facebook Google Microsoft YahooViews 1459

Problem Statement

Peeking Iterator LeetCode Solution – 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.

Example

Test Case 1:

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

Peeking Iterator LeetCode Solution

Approach:

Idea:

This is more design problem, not an algorithmic one in my opinion. You have already given implemented class iterator, which you can understand as a list, but it is not a list. The goal is to implement the so-called peeking iterator and to do this we need to be one step ahead: let us create self.buffer variable, which will keep the next value from our iterator.

  1. When we call peek function, we just return value from our buffer.
  2. When we call next function, we write buffer variable to tmp, then we update our buffer: if we have the next element, we go to the next element, if we do not have it we make it equal to None.
  3. Finally, hasNext the function now is just checking if the buffer is empty or not.

Code for Peeking Iterator

Java Program

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    private Iterator<Integer> iterator;
    private Integer temp;

        public PeekingIterator(Iterator<Integer> iterator) {
            this.iterator = iterator;
        }
        
    // Returns the next element in the iteration without advancing the iterator.
        public Integer peek() {
        if (!hasNext()) return null;
        if (temp == null) {
            temp = iterator.next();
        }
        return temp;
        }
        
        // hasNext() and next() should behave the same as in the Iterator interface.
        // Override them if needed.
        @Override
        public Integer next() {
        if (!hasNext()) return null;
        if (temp == null) {
            Integer next = iterator.next();
            return next;
        } else {
            Integer next = temp;
            temp = null;
                return next;
        }
        }
        
        @Override
        public boolean hasNext() {
            return temp != null || iterator.hasNext();
        }
}

Python Program

# Below is the interface for Iterator, which is already defined for you.
#
# class Iterator(object):
#     def __init__(self, nums):
#         """
#         Initializes an iterator object to the beginning of a list.
#         :type nums: List[int]
#         """
#
#     def hasNext(self):
#         """
#         Returns true if the iteration has more elements.
#         :rtype: bool
#         """
#
#     def next(self):
#         """
#         Returns the next element in the iteration.
#         :rtype: int
#         """

class PeekingIterator:
    def __init__(self, iterator):
        self.iterator = iterator
        self.buffer = self.iterator.next() if self.iterator.hasNext() else None
        
    def peek(self):
        return self.buffer
        
    def next(self):
        tmp = self.buffer
        self.buffer = self.iterator.next() if self.iterator.hasNext() else None
        return tmp
        
    def hasNext(self):
        return self.buffer != None
        

# Your PeekingIterator object will be instantiated and called as such:
# iter = PeekingIterator(Iterator(nums))
# while iter.hasNext():
#     val = iter.peek()   # Get the next element but not advance the iterator.
#     iter.next()         # Should return the same value as [val].

Complexity Analysis for Peeking Iterator LeetCode Solution

Time complexity: O(1)

Space complexity: O(1)

Reference: https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

Translate »