Peeking Iterator

Design an iterator with peek functionality, adding to the standard next and hasNext operations for efficient element access.

array design iterator

Problem Statement

In this problem, you are asked to design a PeekingIterator class. This iterator is a modification of an existing iterator that supports three functions: next(), hasNext(), and peek(). The next() function returns the next element in the iteration, while hasNext() checks if more elements remain. The peek() function returns the next element without advancing the iterator.

To implement the PeekingIterator class, you must ensure that peek() does not change the iterator's state or move the pointer forward. The solution should efficiently manage the next element, storing it temporarily to allow peek without disrupting the normal flow of iteration.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
All the calls to next and peek are valid.
At most 1000 calls will be made to next, hasNext, and peek.

Solution Approach

Cache the Next Element

The most straightforward approach involves caching the next element as soon as next() is called. This allows peek() to access the next element without moving the iterator pointer forward. This approach uses a temporary variable to store the next element, ensuring that peek() works without side effects.

Modify the Iterator with peek()

You will need to adapt the iterator to return the cached element for peek() and update the cache with the subsequent element when next() is called. This ensures that peek always reflects the next element in the sequence without needing extra logic for every peek call.

Handle Edge Cases

Consider the edge cases, such as when the iterator has no more elements. The iterator should handle these cases gracefully, with hasNext() correctly returning false and preventing peek or next from being called when there's no more data.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for each of the next, hasNext, and peek operations is O(1), since each operation is done in constant time. Space complexity depends on the number of elements cached, which is O(1) since we only store one element at a time for peek functionality.

What Interviewers Usually Probe

Look for understanding of iterator design patterns and the need for efficient caching.
Test the candidate's ability to handle edge cases like empty or fully traversed iterators.
Gauge how well the candidate manages state within the iterator, ensuring peek() doesn't disrupt the iterator's flow.

Common Pitfalls or Variants

Common pitfalls

Failing to properly cache the next element, leading to incorrect results from peek().
Not handling edge cases like calling next or peek when there are no remaining elements.
Overcomplicating the solution by storing unnecessary state, increasing space complexity.

Follow-up variants

Designing an iterator with more advanced peek features, such as peeking multiple steps ahead.
Adding support for resetting the iterator back to the start after completing the iteration.
Expanding the iterator's functionality to support different data types, like strings or custom objects.

FAQ

How do I efficiently implement the peek function for the PeekingIterator?

To implement peek efficiently, store the next element in a temporary variable as soon as next() is called, and return that element during peek() without advancing the iterator.

What is the time complexity for the next and peek operations?

Both next() and peek() operate in constant time, O(1), because each call only requires accessing or updating the cached next element.

How should I handle calling next() or peek() when there are no more elements?

You should ensure that hasNext() correctly returns false, and prevent calling next() or peek() when there are no remaining elements to avoid errors.

What are the edge cases I should consider in PeekingIterator?

Edge cases include handling an empty iterator, reaching the end of the sequence, and ensuring peek() behaves correctly after calling next().

How does the caching technique help with the peek functionality?

Caching allows peek() to access the next element without advancing the iterator, enabling a quick and efficient preview of the next item in the sequence.

terminal

Solution

Solution 1

#### Python3

# 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].

Continue Practicing

#900 rle iterator #303 range sum query immutable #304 range sum query 2d immutable