We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Peeking Iterator

Number: 284

Difficulty: Medium

Paid? No

Companies: TikTok, Meta, Apple, Google, Yahoo

Problem Description

Design an iterator that supports the peek operation on an existing iterator in addition to the next and hasNext operations. Implement a PeekingIterator class that pre-fetches the next element so that peek returns it without advancing the pointer.

Key Insights

  • Use a buffered variable as a cache to store the next element.
  • The peek method retrieves the cached element without modifying the underlying iterator.
  • The next method returns the cached element (if available) and then updates the cache with the subsequent element.
  • The hasNext method checks if the buffer has an element or if the underlying iterator has more elements.

Space and Time Complexity

Time Complexity: O(1) per operation (peek, next, and hasNext)
Space Complexity: O(1) additional space to store the cached element.

Solution

The approach is to maintain a single cached variable (buffer) that always holds the next element if one exists. During initialization, the cache is empty. The peek() method checks if the cache is populated; if not, it fetches the next element from the underlying iterator and caches it. The next() method returns the cached element if present and then refreshes the cache with the next element if possible. Otherwise, it directly returns the next element from the iterator. This lookahead mechanism ensures that peek() can always return the next element without advancing the iterator's pointer, allowing next() and hasNext() to behave as expected.

Code Solutions

class PeekingIterator:
    def __init__(self, iterator):
        # Initialize the PeekingIterator with the given iterator.
        self.iterator = iterator
        self._has_peeked = False
        self._peeked_value = None

    def peek(self):
        # If we haven't peeked yet, fetch the next element and cache it.
        if not self._has_peeked:
            self._peeked_value = next(self.iterator)
            self._has_peeked = True
        return self._peeked_value

    def next(self):
        # If there's a cached element, return it and clear the cache.
        if self._has_peeked:
            next_elem = self._peeked_value
            self._peeked_value = None
            self._has_peeked = False
            return next_elem
        # Otherwise, return the next element from the iterator.
        return next(self.iterator)

    def hasNext(self):
        # If element is cached, then there is a next element.
        if self._has_peeked:
            return True
        # Try to fetch the next element to update the cache.
        try:
            self._peeked_value = next(self.iterator)
            self._has_peeked = True
            return True
        except StopIteration:
            return False
← Back to All Questions