1945. An Iterator With Exactly One Undo

A source hands out n values in order. Wrap it so that the LAST value returned can be put back, but only ever one.

next print the next value and consume it undo put the last returned value back and print it peek print the next value without consuming it hasnext print yes or no

## The rules, so the answer is decidable

• next prints done when the source is exhausted.
• undo prints the value it put back. It prints no when there is nothing to
• put back, and after an undo the next next returns that value again.
• There is EXACTLY ONE step of undo. Two undo operations in a row means the
• second one prints no, even if many values have already been returned.
• A next that printed done leaves nothing to undo, so an undo straight
• after it prints no.
• peek never changes anything, including whether an undo is available.

``` values 1 2 3 4

next -> 1 next -> 2 undo -> 2 2 goes back; the permission is now spent undo -> no only one step is available next -> 2 the value that was put back comes out again peek -> 3 next -> 3 hasnext -> yes ```

## What most people try first

A stack of everything returned so far, popping on undo. That is the natural reading of the word, it is strictly easier than what is asked, and it is wrong: the second consecutive undo rewinds again instead of refusing. The bound is the problem. An unlimited undo needs no extra state at all, because the cursor alone tells you where to go back to, whereas a single step needs something that records whether the step is still available.

The second mistake is subtler. Having noticed that a flag is needed, people set it on every next and clear it on every undo, and forget the next that printed done. That next returned nothing, so there is nothing to put back, but the flag left standing from an earlier next says otherwise and the undo rewinds a value that was already handed back.

## A cursor and one boolean

``` at how many values have been returned, so the next one is values[at] can whether the last operation earned a rewind

next: if at < n -> print values[at], at += 1, can = true otherwise -> print done, can = false undo: if can -> at -= 1, can = false, print values[at] otherwise -> print no peek: values[at], or done; can is untouched hasnext: whether at < n ```

Two things make this correct rather than merely plausible. can is written by every operation that could change it, including the exhausted next, so it is never stale. And undo clears can BEFORE anything else can read it, which is what makes the second consecutive undo refuse.

## Why it is correct

The claim is that can is true exactly when a rewind is legal, which means the immediately preceding operation was a next that returned a value and no undo has consumed it. Each operation maintains that directly: a returning next sets it, an exhausted next clears it, an undo clears it, and peek and hasnext cannot change what the preceding operation was in a way that matters, because neither of them returns a value that could be put back.

It also follows that at never goes below zero. An undo only runs when can is true, and can is only true after a next that incremented at, so there is always something to step back over. No separate bounds check is needed, and writing one would hide the real invariant.

## The boundary that breaks a careless implementation

An undo as the very first operation, which must print no, and an undo after the source has run out, which must also print no. Both are cases where a cursor-only implementation looks correct and a flag-only implementation does not.

## Overflow

Values reach 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647. The cursor reaches 200000. Nothing is added or multiplied, so there is no intermediate large enough to overflow anything; the values are carried and printed, never combined.

## Cost

O(1) for every operation and O(n) memory for the values, so the run is O(n + q). The judge cannot enforce the per-operation bound, but nothing slower than constant time is natural here: the interesting failure in this problem is wrong, not slow.

Constraints - `0 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤` each value `≤ 1000000000` - every operation runs in `O(1)`