284. Peeking Iterator
Problem Description
The task is to design a PeekingIterator
that extends the functionality of a standard iterator. Unlike a regular iterator that only supports next
and hasNext
operations, the PeekingIterator
should also support a peek
operation. The peek
method allows the user to look at the next element the iterator would return without actually moving the iterator forward. This can be particularly useful when you need to make decisions based on the next item without actually removing it from the iteration sequence.
Intuition
The intuitive approach to solving this problem involves caching the next element of the iterator after a peek
call, because a regular iterator would not allow us to see the next element without advancing to it. Thus, we need an additional state in PeekingIterator
to remember whether we’ve peeked at the next element and what that element is.
Here is a step-by-step break-down of the intuition behind the solution:
-
Initialize State: When we create a
PeekingIterator
, we store the originalIterator
and initialize a state indicating whether the iterator has been peeked or not (has_peeked
), and a variable to store the peeked value (peeked_element
). -
Peek Operation: For the
peek
function we check if we have already called apeek
without a subsequentnext
. If we haven’t peeked yet (has_peeked
isFalse
), we callnext
on the underlying iterator and store the value. We then return this stored value without changing the position of the underlying iterator. -
Next Operation: If a
peek
has not occurred, the regularnext
operation of the underlying iterator is used. If we've already peeked (has_peeked
isTrue
), we need to return the storedpeeked_element
and reset our state so the iterator can advance whennext
is called again. -
HasNext Operation: For the
hasNext
method, we simply returnTrue
if we are in the peeked state (as we already have a next element), or we defer to the underlying iterator'shasNext
method.
The critical part of this solution is to carefully manage the has_peeked
and peeked_element
variables so as to not lose track of the iterator's state or prematurely advance the underlying iterator.
Solution Approach
The solution involves implementing a wrapper class around the provided iterator to support the additional peek
operation. We make use of the object-oriented concept of class to create our own PeekingIterator
that maintains some internal state.
Here's a step-by-step walk through the implementation:
-
Initialization: In the constructor (
__init__
method), we accept anIterator
as an argument. We then initialize two instance variables:self.has_peeked
: A boolean that indicates if we have already peeked at the next element.self.peeked_element
: An integer to hold the next element after a peek. These variables are critical to manage the state between successivepeek
andnext
calls.
-
Peek: The
peek
method checks if we have already peeked (self.has_peeked
), and if not, it 'peeks' ahead by callingnext
on the stored iterator, saving this value toself.peeked_element
and settingself.has_peeked
toTrue
. The value ofself.peeked_element
is returned. -
Next: In the
next
method, we first check ifself.has_peeked
isTrue
. If it is, we already have a peeked element to return, which we do. We then resetself.has_peeked
toFalse
andself.peeked_element
toNone
to reflect that we no longer have a peeked value. Ifself.has_peeked
isFalse
, we directly return the next element from the underlying iterator. -
HasNext: For
hasNext
, we returnTrue
if eitherself.has_peeked
isTrue
(since we have a peeked element ready) or if the underlying iterator has more elements, as indicated by itshasNext
method.
This implementation uses lazy evaluation for the peek
operation. The element is not advanced until necessary (i.e., until the next
method is called). This strategy minimizes the number of calls to the underlying iterator's next
method, as it only advances the iterator when we're certain we need to consume an element. This approach effectively implements a look-ahead buffer with a capacity of one element.
Such an implementation could be useful in scenarios like comparison-based sorting or merging, where you might need to compare the next item without yet removing it from the iterator.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach:
Suppose we have an iterator over a collection with elements [1, 2, 3]
. When we wrap this iterator with the PeekingIterator
, here's how we can interact with it and what happens internally:
-
We instantiate
PeekingIterator
with our iterator.self.has_peeked
is initialized toFalse
, andself.peeked_element
is initialized toNone
. -
We call
peek()
method. Sinceself.has_peeked
isFalse
, thenext()
method is called on the underlying iterator, giving us1
. Nowself.peeked_element
becomes1
, andself.has_peeked
is nowTrue
. Thepeek()
method returns1
, but our iterator's position hasn't advanced. -
We call the
next()
method. Asself.has_peeked
isTrue
, it will returnself.peeked_element
, which is1
. After this,self.has_peeked
is set toFalse
andself.peeked_element
toNone
. The underlying iterator's next element is now2
. -
We call
peek()
again. The process from step 2 repeats;self.peeked_element
is set to2
,self.has_peeked
becomesTrue
, and the method returns2
. -
We call
next()
. Sinceself.has_peeked
isTrue
,self.peeked_element
(which is2
) is returned. Bothself.has_peeked
andself.peeked_element
are reset as before. -
We call
hasNext()
. Sinceself.has_peeked
isFalse
, we check with the underlying iterator, which still has an element (which is3
), sohasNext()
returnsTrue
. -
We call
next()
and receive3
, which is the last element of the iterator. -
Finally, when we call
hasNext()
again, it returnsFalse
because bothself.has_peeked
isFalse
and the underlying iterator has no further elements.
This example did not include calls to hasNext()
prior to next()
or peek()
calls, but in practice, the hasNext()
method can be used anytime to check if there is a next element available before calling next()
or peek()
to avoid exceptions from reaching the end of the iterator.
Solution Implementation
1class Iterator:
2 # A class that represents an iterator.
3 def __init__(self, nums):
4 """
5 Initialize the iterator object to the beginning of a list.
6
7 :param nums: A list of integers.
8 """
9 # Your Iterator class here.
10
11 def has_next(self):
12 """
13 Checks if the iteration has more elements.
14
15 :return: True if there are more elements, False otherwise.
16 """
17 # Your has_next logic here.
18
19 def next(self):
20 """
21 Returns the next element in the iteration.
22
23 :return: The next integer in the iteration.
24 """
25 # Your next logic here.
26
27
28class PeekingIterator:
29 def __init__(self, iterator):
30 """
31 Initialize a PeekingIterator with an iterator.
32
33 :param iterator: An instance of the Iterator class.
34 """
35 self.iterator = iterator
36 self.peeked_element = None # The element that has been peeked at.
37 self.has_peeked = False # Flag to check if we have a peeked element.
38
39 def peek(self):
40 """
41 Returns the next element in the iteration without advancing the iterator.
42
43 :return: The next integer in the iteration.
44 """
45 if not self.has_peeked:
46 # If we haven't peeked yet, retrieve the next element
47 self.peeked_element = self.iterator.next()
48 self.has_peeked = True # Set the flag to indicate that we have peeked
49 return self.peeked_element
50
51 def next(self):
52 """
53 Returns the next element and advances the iterator.
54
55 :return: The next integer in the iteration.
56 """
57 if not self.has_peeked:
58 # If we haven't peeked, we simply get the next element from the iterator
59 return self.iterator.next()
60
61 # If we have peeked, we return the peeked element and reset the peeked state
62 result = self.peeked_element
63 self.peeked_element = None
64 self.has_peeked = False
65 return result
66
67 def has_next(self):
68 """
69 Checks if there are more elements in the iteration.
70
71 :return: True if there are more elements, False otherwise.
72 """
73 # We have an element if we already peeked or if the iterator has more elements
74 return self.has_peeked or self.iterator.has_next()
75
76
77# Usage example
78# iter = PeekingIterator(Iterator(nums))
79# while iter.has_next():
80# val = iter.peek() # View the next element but do not advance the iterator.
81# iter.next() # Should return the same value as [val].
82
1import java.util.Iterator;
2
3// The PeekingIterator class wraps a standard Iterator and allows for peeking ahead at the next element without advancing the iterator.
4public class PeekingIterator implements Iterator<Integer> {
5 private Iterator<Integer> iterator; // An iterator over a collection of Integers
6 private boolean hasPeeked; // A flag indicating if we've already peeked at the next element
7 private Integer peekedElement; // The next element, if we've peeked
8
9 // Constructor initializes the PeekingIterator using an existing Iterator.
10 public PeekingIterator(Iterator<Integer> iterator) {
11 this.iterator = iterator;
12 }
13
14 // The peek method returns the next element in the iteration without advancing the iterator.
15 public Integer peek() {
16 if (!hasPeeked) {
17 if (iterator.hasNext()) {
18 peekedElement = iterator.next(); // Store the next element so we can return it later
19 } else {
20 throw new NoSuchElementException(); // In case there are no more elements to peek
21 }
22 hasPeeked = true;
23 }
24 return peekedElement;
25 }
26
27 // The next method should behave the same as if using the Iterator directly.
28 @Override
29 public Integer next() {
30 if (!hasPeeked) {
31 return iterator.next(); // Directly return the next element from the iterator
32 }
33 Integer result = peekedElement; // Return the stored peeked element
34 hasPeeked = false; // Reset the peeked flag
35 peekedElement = null; // Clear the stored element
36 return result;
37 }
38
39 // The hasNext method indicates whether the iteration has more elements.
40 @Override
41 public boolean hasNext() {
42 return hasPeeked || iterator.hasNext(); // Return true if we've peeked or if the iterator has more elements
43 }
44}
45
1class PeekingIterator : public Iterator {
2private:
3 bool hasPeeked; // Flag to check if we already peeked at the next element
4 int peekedValue; // Stores the value of the peeked element if hasPeeked is true
5
6public:
7 PeekingIterator(const vector<int>& nums)
8 : Iterator(nums), hasPeeked(false)
9 {
10 // Constructor inherits from the Iterator and initializes hasPeeked flag to false.
11 // Note that initialization of hasPeeked is done above in the member initializer list.
12 }
13
14 // Peek method allows us to see what the next element in the iterator is without advancing the iterator.
15 int peek() {
16 if (!hasPeeked) {
17 // If we haven't already peeked, fetch the next element and set the hasPeeked flag
18 peekedValue = Iterator::next(); // Get the next element from the iterator
19 hasPeeked = true; // Set the peek flag
20 }
21 return peekedValue; // Return the peeked value
22 }
23
24 // Override the next() method to consider if we have already peeked at the next element.
25 int next() {
26 if (!hasPeeked) {
27 // If we haven't peeked, return the next element from the iterator directly
28 return Iterator::next();
29 }
30 // If there is a peeked value, reset the hasPeeked flag since next() consumes the peeked element
31 hasPeeked = false;
32 return peekedValue; // Return the peeked value which is the next element
33 }
34
35 // Override the hasNext() method to consider the peek scenario.
36 bool hasNext() const {
37 // If either we have a peeked element or if the underlying iterator has a next element,
38 // we have a next element
39 return hasPeeked || Iterator::hasNext();
40 }
41};
42
1let hasPeeked: boolean = false; // Flag to check if we already peeked at the next element
2let peekedValue: number; // Stores the value of the peeked element if hasPeeked is true
3let iterator: Iterator<number>; // The iterator instance which is adapted by the PeekingIterator functionality
4
5function PeekingIterator(nums: number[]) {
6 // Initialize the iterator with nums.
7 iterator = nums[Symbol.iterator]();
8}
9
10function peek(): number {
11 if (!hasPeeked) {
12 // If we haven't already peeked, fetch the next element and set the hasPeeked flag
13 const result = iterator.next();
14 if (!result.done) {
15 peekedValue = result.value;
16 hasPeeked = true; // Set the peek flag
17 }
18 }
19 return peekedValue; // Return the peeked value
20}
21
22function next(): number {
23 if (!hasPeeked) {
24 // If we haven't peeked, extract the next element from the iterator directly and return it
25 const result = iterator.next();
26 if (!result.done) {
27 return result.value;
28 }
29 } else {
30 // If there is a peeked value, reset the hasPeeked flag since next() consumes the peeked element
31 hasPeeked = false;
32 return peekedValue; // Return the peeked value which is the next element
33 }
34}
35
36function hasNext(): boolean {
37 // If there is a peeked element or if the underlying iterator has a next element, we have a next element
38 return hasPeeked || !iterator.next().done;
39}
40
Time and Space Complexity
Time Complexity:
-
PeekingIterator.__init__(self, iterator)
:- This method only performs some basic variable assignments. The time complexity here is
O(1)
, since no loops or significant operations are involved.
- This method only performs some basic variable assignments. The time complexity here is
-
PeekingIterator.peek(self)
:- If we have not peeked yet (
self.has_peeked
isFalse
), we callself.iterator.next()
once. Since thenext()
operation of the underlying iterator is assumed to beO(1)
, the overall time complexity forpeek()
is alsoO(1)
. If we already have a peeked element, we just return it, which is again anO(1)
operation.
- If we have not peeked yet (
-
PeekingIterator.next(self)
:- When we haven't peeked (
self.has_peeked
isFalse
), the time complexity isO(1)
as it directly returns the next element by calling the iterator'snext()
method. Once we have peeked (self.has_peeked
isTrue
), it involves returning the peeked element and resettinghas_peeked
andpeeked_element
which is alsoO(1)
time.
- When we haven't peeked (
-
PeekingIterator.hasNext(self)
:- This method checks whether there's a next element by either checking the
self.has_peeked
attribute or calling thehasNext()
method of the underlying iterator, both of these operations have a time complexity ofO(1)
.
- This method checks whether there's a next element by either checking the
Space Complexity:
- Overall space complexity of the
PeekingIterator
class:- The additional space used by the
PeekingIterator
class consists of two variables:self.has_peeked
andself.peeked_element
, which take upO(1)
space. The underlying iterator (self.iterator
) object is not counted towards the space complexity as it is an input to the class. Therefore, the space complexity of thePeekingIterator
isO(1)
as it uses a constant amount of extra space.
- The additional space used by the
In conclusion, both the operations peek()
, next()
, and hasNext()
in the PeekingIterator
class have a time complexity of O(1)
and the space complexity of the PeekingIterator
class is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.