DSA problem
Snapshot Array
Implement a SnapshotArray of fixed length that supports point updates and full-array snapshots. The constructor takes a length and initializes every index to 0. set(index, val) updates a single cell. snap() takes a snapshot of the entire array and returns its snap-id — the first snapshot returns 0, the next returns 1, and so on. get(index, snapId) returns the value of array[index] at the moment snapshot snapId was taken.
A literal implementation that copies the entire array on every snap() is correct but catastrophically slow: with length up to 50,000 and up to 50,000 snapshots, the worst case is 2.5×10^9 array copies. We need snap() to be O(1) and get / set to stay cheap, which rules out any full-array materialization.
The standard trick is per-index versioning. Keep one list per index — call it the history of that cell — where each entry is a pair (snapId, value). set(index, val) simply appends (snapId, val) to that index's history (or overwrites the last entry if it was made at the current snapId — an optional optimization). snap() is reduced to incrementing a counter. get(index, snapId) binary-searches the index's history for the largest (s, v) whose s <= snapId and returns v, defaulting to 0 if no history exists.
This gives O(1) snap, O(1) amortized set, and O(log K) get where K is the number of writes to that specific index — far smaller than the array length. Total memory is proportional to the number of writes, not the product of array length × snapshots, which is the whole point of the design.
Examples
SnapshotArray(3); set(0, 5); snap(); set(0, 6); get(0, 0)5set(0, 4); snap(); set(0, 10); snap(); set(1, 7); get(0, 1)10SnapshotArray(2); snap(); snap(); get(1, 1)0Constraints
- 1 <= length <= 5 * 10^4
- 0 <= index < length
- 0 <= val <= 10^9
- 0 <= snap_id < (the total number of times we call snap())
- At most 5 * 10^4 calls will be made to set, snap, and get.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.