Leetcode #284: Peeking Iterator
In this guide, we solve Leetcode #284 Peeking Iterator in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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
nums) Initializes the object with the given integer iterator iterator.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Design, Array, Iterator
Intuition
We need to support multiple operations efficiently, so the internal design matters most.
Choosing the right combination of structures is the key to meeting the constraints.
Approach
List the required operations and select data structures that optimize them.
Implement each operation with clear invariants.
Steps:
- List the required operations.
- Pick supporting structures.
- Implement methods with clear invariants.
Example
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
Python Solution
# Below is the interface for Iterator, which is already defined for you.
#
# class Iterator:
# 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):
"""
Initialize your data structure here.
:type iterator: Iterator
"""
self.iterator = iterator
self.has_peeked = False
self.peeked_element = None
def peek(self):
"""
Returns the next element in the iteration without advancing the iterator.
:rtype: int
"""
if not self.has_peeked:
self.peeked_element = self.iterator.next()
self.has_peeked = True
return self.peeked_element
def next(self):
"""
:rtype: int
"""
if not self.has_peeked:
return self.iterator.next()
result = self.peeked_element
self.has_peeked = False
self.peeked_element = None
return result
def hasNext(self):
"""
:rtype: bool
"""
return self.has_peeked or self.iterator.hasNext()
# 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
The time complexity is Varies by operation. The space complexity is Varies by operation.
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.