Peeking Iterator

medium design iterator

Problem

Design an iterator that supports the peek() operation in addition to next() and hasNext() — peek() returns the next element without consuming it.

Inputiter over [1,2,3]; peek, next, next, peek, next

Output[1, 1, 2, 3, 3]

peek doesn't advance; next does.

list (comma-separated)

ops (peek/next, comma-separated)

class PeekingIterator:
    def __init__(self, iterator):
        self.it = iterator
        self.cache = next(self.it, None)
    def peek(self): return self.cache
    def next(self):
        v = self.cache
        self.cache = next(self.it, None)
        return v
    def hasNext(self): return self.cache is not None

class PeekingIterator {
  constructor(iter) {
    this.iter = iter[Symbol.iterator]();
    this.cache = this.iter.next();
  }
  peek() { return this.cache.value; }
  next() {
    const v = this.cache.value;
    this.cache = this.iter.next();
    return v;
  }
  hasNext() { return !this.cache.done; }
}

class PeekingIterator implements Iterator {
    Iterator it; Integer cache;
    public PeekingIterator(Iterator iter) {
        it = iter; cache = it.hasNext() ? it.next() : null;
    }
    public Integer peek() { return cache; }
    @Override public Integer next() {
        Integer v = cache;
        cache = it.hasNext() ? it.next() : null;
        return v;
    }
    @Override public boolean hasNext() { return cache != null; }
}

class PeekingIterator : public Iterator {
    bool has; int cache;
public:
    PeekingIterator(const vector& nums) : Iterator(nums) {
        has = Iterator::hasNext();
        if (has) cache = Iterator::next();
    }
    int peek() { return cache; }
    int next() { int v = cache; has = Iterator::hasNext(); if (has) cache = Iterator::next(); return v; }
    bool hasNext() const { return has; }
};

Explanation

A plain iterator can only move forward, so once you pull a value out you cannot put it back. The trick to support peek() is to pull the next value one step early and stash it in a cache.

In the constructor we immediately call the underlying iterator once and save the result in self.cache. Now the next value is always sitting ready to look at.

peek() just returns self.cache without changing anything, so the position does not advance. next() returns the cached value but then refills the cache by pulling the following value from the real iterator. hasNext() simply checks whether the cache currently holds a value.

Example: iterating [1,2,3], the cache starts at 1. peek() returns 1 and leaves it. next() returns 1 and refills the cache to 2. Another next() returns 2 and refills to 3. peek() returns 3, and the final next() returns 3 — giving the sequence 1, 1, 2, 3, 3.

Every operation is one stored read plus at most one pull from the source, so all three calls run in O(1) with O(1) extra space.

Time: O(1) per call Space: O(1)