Snapshot Array
Understanding the Problem
We need to design a data structure that behaves like an array but also supports versioning. You can modify the array at any time, but when you call snap(), the current state is "saved." Later, you can query what any element looked like at any previous snapshot.
The constraint that matters is efficiency. Copying the entire array on every snapshot, with up to 50,000 elements and 50,000 operations, would use far more memory than we can afford. The design problem is how to avoid storing redundant data for elements that did not change between snapshots.
Between two consecutive snapshots, only the indices touched by set change. Everything else stays the same. If we record only those changes instead of the full array, the storage drops to the number of modifications, not the array size times the snapshot count. This is the same idea behind copy-on-write in operating systems and version control systems like Git.
Key Constraints:
1 <= length <= 50000-> The array can be large. Copying it on every snap costs O(length) per snap, which dominates the runtime when snaps are frequent. This is the cost the optimal approach removes.- At most
50000calls toset,snap, andget-> The total number of recorded changes is bounded by the number ofsetcalls, so per-index history lists stay short. 0 <= snap_id <total snaps -> Queried snap_ids are always valid, so no bounds checking is needed.0 <= val <= 10^9-> Values fit in a signed 32-bit integer (max ~2.1 x 10^9).
Approach 1: Brute Force (Copy on Snap)
Intuition
Save a full copy of the array every time snap() is called. Then get(index, snap_id) reads the value directly from the stored copy. This is the version-everything strategy: keep a complete snapshot of the state at every save point.
It is correct and simple to reason about, but wasteful. With 50,000 elements and 50,000 snapshots, the copies hold 2.5 billion values, and most are identical to the snapshot before them. The redundant copies are what the next approach eliminates.
Algorithm
- Initialize an array of the given length, filled with zeros.
- On
set(index, val), update the current array at the given index. - On
snap(), make a deep copy of the current array and store it in a list. Return the current snap_id and increment it. - On
get(index, snap_id), returnsnapshots[snap_id][index].
Example Walkthrough
Code
- Time Complexity: O(1) for
setandget, O(length) forsnap. Thesnapoperation copies the entire array, which takes O(length) time and becomes the bottleneck with frequent snapshots. - Space Complexity: O(length * S) where S is the number of snapshots. Each snapshot stores a full copy of the array, which is extremely wasteful when most elements haven't changed.
This approach copies all length elements on every snap, even when a single element changed. The next approach records only the changes themselves.
Approach 2: Store Changes Per Index with Binary Search (Optimal)
Intuition
Instead of copying the array on each snap, store the history per index. For each index, keep a list of its values over time, tagged with the snap_id at which each value took effect. A set records the change against the current snap_id. A snap only increments the snap counter, since no value needs to be copied.
The work moves to get. Given an index and a snap_id, we need the value that index held at that snapshot, which is the value from the most recent set at or before that snap_id. Because snap_ids only increase, each index's history list is already sorted by snap_id, so finding the largest snap_id that is less than or equal to the query is a binary search.
The structure is a per-cell edit log. Rather than save the whole spreadsheet at each version, each cell records only its own edits. To read a cell's value at version 5, scan that cell's log for the latest edit at or before version 5.
The history list for an index holds exactly the snap_ids at which that index was set, in increasing order, since snap_ids only increase and entries are appended in order. The value visible at a query snap_id q is the value written by the last set at or before q, which corresponds to the entry with the largest snap_id <= q. Binary search on the sorted list finds that entry, and the initial (0, 0) entry guarantees a match exists for every valid query.
The cost of the brute force snap() (copying length elements) becomes O(1) here, and the cost moves to get(), which does an O(log S) binary search where S is the number of entries for that index. S is bounded by the number of set calls, so the lists stay short.
Algorithm
- Initialize an array of length
length, where each element stores a list of(snap_id, value)pairs. Start each list with(0, 0)to represent the initial value. - Maintain a
snapCountvariable starting at 0. - On
set(index, val), append or update the entry for the currentsnapCountin the list at that index. If the last entry in the list already has the current snap_id, update its value instead of appending a duplicate. - On
snap(), return the currentsnapCountand increment it. No array copying needed. - On
get(index, snap_id), binary search the list at the given index for the largest snap_id that is less than or equal to the queried snap_id. Return the corresponding value.
Example Walkthrough
Code
- Time Complexity: O(1) for
setandsnap, O(log S) forgetwhere S is the number of entries in the queried index's history. Thesetoperation appends or updates in O(1). Thesnapincrements a counter. Thegetbinary searches the history list. - Space Complexity: O(length + total set calls). We store one initial entry per index, plus one additional entry for each set call that happens after a new snap. This is dramatically better than O(length * S) in the brute force.