algoadvance

Leetcode 284. Peeking Iterator

Problem Statement

284. Peeking Iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that supports the peek() operation.

Implement the PeekingIterator class:

Clarifying Questions

  1. What type does the iterator operate on?
    • The iterator will typically operate on a generic type E.
  2. What should happen if peek() is called when there are no more elements?
    • This should be handled gracefully. Normally, we assume we won’t call peek() or next() if hasNext() is false.
  3. Is it guaranteed that the input iterator is not null?
    • Yes, you can assume the input iterator is not null.

Strategy

To implement the PeekingIterator class, we need to store the next element so that the peek() function can return it without advancing the iterator. This requires maintaining an internal state and ensuring the iterator’s position is only advanced when next() is called.

Here’s a step-by-step strategy:

  1. Store the Iterator: Store the reference of the input iterator.
  2. Preload the First Element: Fetch the first element during the initialization to support peek().
  3. Implement peek() Method: Return the preloaded element without advancing the iterator.
  4. Implement next() Method: Return the preloaded element and fetch the next element for future operations.
  5. Implement hasNext() Method: Simply check if the preloaded element (or cache) is available.

Code Implementation

import java.util.Iterator;

class PeekingIterator<E> implements Iterator<E> {
    private Iterator<E> iterator;
    private E nextElement;
    private boolean hasNext;

    public PeekingIterator(Iterator<E> iterator) {
        this.iterator = iterator;
        if (iterator.hasNext()) {
            nextElement = iterator.next();
            hasNext = true;
        } else {
            hasNext = false;
        }
    }

    public E peek() {
        return nextElement;
    }

    @Override
    public E next() {
        E result = nextElement;
        if (iterator.hasNext()) {
            nextElement = iterator.next();
        } else {
            hasNext = false;
        }
        return result;
    }

    @Override
    public boolean hasNext() {
        return hasNext;
    }
}

Time Complexity

  1. Initialization (PeekingIterator): O(1) – Initializing and preloading the first element is done in constant time.
  2. Peek (peek): O(1) – Simply returns the preloaded element.
  3. Next (next): O(1) – Returns the preloaded element and fetches the next one in constant time.
  4. HasNext (hasNext): O(1) – Simply returns the boolean flag.

The space complexity is O(1) since we are using a minimal amount of extra space for storing the element and a boolean flag.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI