602/670

602. Snapshot Array

Medium

Design an array that can be photographed: at any moment you can take a snapshot, and later read what any cell contained at the time of any past snapshot.

Implement the class SnapshotArray:

SnapshotArray(length) — creates an array of length cells, every cell holding 0.
set(index, val) — writes val into cell index (affects the present only, never past snapshots).
snap() — takes a snapshot and returns its id: the number of snap calls made before this one, so ids count up from 0.
get(index, snap_id) — returns the value cell index held at the moment snapshot snap_id was taken.

Each get call is guaranteed to reference a snapshot that has already been taken.

Example 1:

Input: SnapshotArray(3); set(0, 5); snap(); set(0, 6); get(0, 0)

Output: snap() → 0, get(0, 0) → 5

Explanation: The first snap returns id 0. Overwriting cell 0 with 6 afterward does not disturb the photo, so get(0, 0) still sees 5.

Example 2:

Input: SnapshotArray(1); set(0, 4); set(0, 16); snap(); get(0, 0); set(0, 13); snap(); get(0, 1)

Output: snap() → 0, get(0, 0) → 16, snap() → 1, get(0, 1) → 13

Explanation: Cell 0 is overwritten to 16 before the first snapshot, so snapshot 0 records 16. The later write of 13 lands in snapshot 1.

Constraints:

1 ≤ length ≤ 5 * 10⁴
0 ≤ index < length
0 ≤ val ≤ 10⁹
At most 5 * 10⁴ calls are made to set, snap, and get combined.
Every get references a snap_id that snap has already returned.

Hints:

Copying the whole array on every snap works, but a snap costs O(length) even when nothing changed. Notice that most cells never change between snapshots — can you store only the changes?

Give every cell its own history: a list of (snapshot-era, value) pairs, appending only when the cell is actually written. snap() then just increments a counter — O(1).

A cell's history is sorted by era, so get(index, snap_id) is a binary search: find the rightmost pair whose era is <= snap_id. Seed each history with (-1, 0) so unwritten cells resolve to 0.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: SnapshotArray(3); set(0, 5); snap(); set(0, 6); get(0, 0)

Expected output: [0, 5]