algoadvance

Leetcode 284. Peeking Iterator

Problem Statement

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that supports the peek() operation. The peek() method should return the next element in the iteration without advancing the iterator. The PeekingIterator should still support the standard operations of advancing the iterator with next() and checking if there are elements remaining using hasNext().

Example:

Input:
[1, 2, 3]
Output:
[null, 1, 1, 2, 2, 3, false]
Explanation:
PeekingIterator peekIterator = new PeekingIterator([1, 2, 3]);
peekIterator.next();    // return 1
peekIterator.peek();    // return 2
peekIterator.next();    // return 2
peekIterator.next();    // return 3
peekIterator.hasNext(); // return false

Clarifying Questions

  1. Is the input a continuous stream or a fixed list of elements?
    • The input is a fixed list of elements.
  2. What should peek() return when the iterator is at the end?
    • The expected behavior for peek() when no elements are left to iterate should be addressed explicitly, but typically if hasNext() is false, calling peek() would likely be undefined or might throw an exception.
  3. Can the iterator contain duplicate elements?
    • Yes, the iterator can contain duplicate elements, as peek() and next() operations should be based on their positions, not the element values.

Code

#include <vector>

// Below is the Iterator interface implementation. Do not change it.
class Iterator {
    struct Data;
    Data* data;
public:
    Iterator(const std::vector<int>& nums);
    Iterator(const Iterator& iter);
    virtual ~Iterator();
    // Returns the next element in the iteration.
    int next();
    // Returns true if the iteration has more elements.
    bool hasNext() const;
};

class PeekingIterator : public Iterator {
private:
    int nextElement;
    bool hasNextElement;
public:
    PeekingIterator(const std::vector<int>& nums) : Iterator(nums) {
        hasNextElement = Iterator::hasNext();
        if (hasNextElement) {
            nextElement = Iterator::next();
        }
    }

    // Returns the next element in the iteration without advancing the iterator.
    int peek() {
        return nextElement;
    }

    // Override next() to use the cached element.
    int next() {
        int toReturn = nextElement;
        hasNextElement = Iterator::hasNext();
        if (hasNextElement) {
            nextElement = Iterator::next();
        }
        return toReturn;
    }

    // Override hasNext() to include the logic for the cached element.
    bool hasNext() const {
        return hasNextElement;
    }
};

Strategy

  1. Initialization: The PeekingIterator is initialized with a given list of elements. It uses the base Iterator constructor to initialize the iterator.
  2. Caching Next Element: During initialization, the first element is fetched and stored in nextElement. A boolean hasNextElement is used to keep track of whether any elements are left to iterate.
  3. peek() Method: This method simply returns the cached nextElement without advancing the iterator.
  4. next() Method: This method returns the cached nextElement and advances the iterator by fetching the next element into the cache.
  5. hasNext() Method: This method checks the boolean hasNextElement to determine if there are more elements to iterate.

Time Complexity

This design ensures that all operations (peek, next, hasNext) perform efficiently with constant time complexity.

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