# LeetCode 284: Peeking Iterator

## Problem Restatement

We are given an existing iterator with these operations:

```python
next()
hasNext()
```

We need to design a new iterator called `PeekingIterator` that also supports:

```python
peek()
```

`peek()` should return the next element without moving the iterator forward.

That means calling:

```python
peek()
```

multiple times should always return the same value until:

```python
next()
```

is called.

The official statement defines `peek()` as retrieving the next element without advancing the iterator. The wrapped iterator already supports `next()` and `hasNext()`. ([leetcode.com](https://leetcode.com/problems/peeking-iterator/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Wrapped iterator | Existing iterator object |
| `peek()` | Returns next value without consuming it |
| `next()` | Returns next value and advances |
| `hasNext()` | Returns whether more values exist |

Class shape:

```python
class PeekingIterator:
    def __init__(self, iterator):
        ...

    def peek(self):
        ...

    def next(self):
        ...

    def hasNext(self):
        ...
```

## Examples

Suppose the underlying iterator contains:

```python
[1, 2, 3]
```

Calls behave like this:

| Call | Return | Iterator Position |
|---|---|---|
| `peek()` | `1` | unchanged |
| `peek()` | `1` | unchanged |
| `next()` | `1` | moves forward |
| `next()` | `2` | moves forward |
| `peek()` | `3` | unchanged |
| `hasNext()` | `True` | unchanged |
| `next()` | `3` | moves forward |
| `hasNext()` | `False` | unchanged |

The important behavior is:

```python
peek()
```

does not consume the element.

## First Thought: Call next() Inside peek()

A naive idea is:

```python
def peek(self):
    return self.iterator.next()
```

But this is incorrect.

Calling:

```python
next()
```

advances the iterator.

So after one `peek()`, the element would already be consumed.

Example:

```python
peek() -> 1
next() -> 2
```

This violates the required behavior.

We need a way to remember the next value before it is consumed.

## Key Insight

Always cache the next element.

When the `PeekingIterator` is created:

1. Read the first value from the underlying iterator.
2. Store it in a variable called `next_value`.

Now:

```python
peek()
```

simply returns the cached value.

When:

```python
next()
```

is called:

1. Return the cached value.
2. Advance the underlying iterator once.
3. Update the cache.

So the cache always stores the next unread value.

## Algorithm

During initialization:

If the underlying iterator has another value:

```python
self.next_value = iterator.next()
```

Otherwise:

```python
self.next_value = None
```

For `peek()`:

```python
return self.next_value
```

For `next()`:

1. Save the current cached value.
2. Advance the wrapped iterator.
3. Refresh the cache.
4. Return the saved value.

For `hasNext()`:

```python
return self.next_value is not None
```

## Correctness

At all times, `next_value` stores the next unread element from the underlying iterator, or `None` if no elements remain.

During initialization, the algorithm reads the first unread element and stores it in `next_value`. So the invariant holds initially.

`peek()` simply returns `next_value` without changing either the cache or the underlying iterator. Therefore the iterator position remains unchanged.

When `next()` is called, the algorithm returns the current cached value. This is exactly the next unread element.

Then the algorithm advances the wrapped iterator once and updates the cache to the following unread element, or `None` if no element remains.

So after every operation, `next_value` continues to store the next unread element.

Therefore:

- `peek()` always returns the correct next element without consuming it.
- `next()` always returns the correct next element and advances exactly once.
- `hasNext()` correctly reports whether unread elements remain.

## Complexity

| Operation | Time | Space | Why |
|---|---|---|---|
| Constructor | `O(1)` | `O(1)` | Stores one cached value |
| `peek()` | `O(1)` | `O(1)` | Returns cached value |
| `next()` | `O(1)` | `O(1)` | One iterator advance |
| `hasNext()` | `O(1)` | `O(1)` | Cache existence check |

## Implementation

```python
class PeekingIterator:
    def __init__(self, iterator):
        self.iterator = iterator

        if iterator.hasNext():
            self.next_value = iterator.next()
        else:
            self.next_value = None

    def peek(self):
        return self.next_value

    def next(self):
        value = self.next_value

        if self.iterator.hasNext():
            self.next_value = self.iterator.next()
        else:
            self.next_value = None

        return value

    def hasNext(self):
        return self.next_value is not None
```

## Code Explanation

We store the wrapped iterator:

```python
self.iterator = iterator
```

Then we preload the first unread value:

```python
if iterator.hasNext():
    self.next_value = iterator.next()
```

This creates the cache.

If no value exists:

```python
self.next_value = None
```

The `peek()` method simply returns the cached value:

```python
return self.next_value
```

without advancing anything.

In `next()`:

```python
value = self.next_value
```

stores the value we will return.

Then we refresh the cache:

```python
if self.iterator.hasNext():
    self.next_value = self.iterator.next()
else:
    self.next_value = None
```

Finally:

```python
return value
```

returns the old cached element.

`hasNext()` checks whether the cache still contains an unread value:

```python
return self.next_value is not None
```

## Alternative Lazy Peek Design

Another design delays caching until the first `peek()` call.

This uses an additional flag:

```python
self.has_peeked
```

and only fetches the value when needed.

However, the eager preload version is simpler because:

- `peek()` becomes trivial.
- `hasNext()` becomes simple.
- State transitions are easier to reason about.

So the preload cache design is usually preferred.

## Testing

```python
class Iterator:
    def __init__(self, nums):
        self.nums = nums
        self.index = 0

    def hasNext(self):
        return self.index < len(self.nums)

    def next(self):
        value = self.nums[self.index]
        self.index += 1
        return value

def test_peeking_iterator():
    it = PeekingIterator(Iterator([1, 2, 3]))

    assert it.peek() == 1
    assert it.peek() == 1

    assert it.next() == 1
    assert it.next() == 2

    assert it.peek() == 3
    assert it.hasNext() is True

    assert it.next() == 3
    assert it.hasNext() is False

    print("all tests passed")

test_peeking_iterator()
```

Test meaning:

| Test | Why |
|---|---|
| Multiple `peek()` calls | Confirms no advancement |
| `next()` after `peek()` | Confirms correct value returned |
| Final `hasNext()` | Confirms iterator exhaustion |
| Mixed operations | Confirms cache updates correctly |