Snapshot Array
Last Updated: March 29, 2026
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 tricky part is efficiency. A naive approach might copy the entire array on every snapshot, but with up to 50,000 elements and 50,000 operations, that could use a massive amount of memory. The key question is: how do we avoid storing redundant data for elements that haven't changed between snapshots?
The core observation is that most elements don't change between consecutive snapshots. If we only track the changes (which indices were actually modified), we can save enormous amounts of space. This is the same insight behind copy-on-write in operating systems and version control systems like Git.
Key Constraints:
1 <= length <= 50000-> The array can be fairly large. Copying the entire array on every snap would be O(length) per snap, which is expensive if snaps are frequent.- At most
50000calls toset,snap, andget-> Total operations are moderate. We need each operation to be efficient, but we're not dealing with millions of calls. 0 <= snap_id <total snaps -> We'll always query valid snap_ids, so no need for error handling on invalid ids.0 <= val <= 10^9-> Values fit in a standard 32-bit integer.
Approach 1: Brute Force (Copy on Snap)
Intuition
The most straightforward way to implement snapshots is to literally save a copy of the entire array every time snap() is called. Then get(index, snap_id) just looks up the value in the saved copy. This is exactly what you'd do if someone said "save your document" -- you'd make a full copy.
It's simple and correct, but wasteful. If the array has 50,000 elements and we take 50,000 snapshots, we're storing 2.5 billion values. Most of those values didn't change between snapshots, so we're wasting memory on redundant copies.
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 if only one element changed. What if we only recorded the changes that actually happened?
Approach 2: Store Changes Per Index with Binary Search (Optimal)
Intuition
Instead of copying the entire array on each snap, flip the perspective. For each index, maintain a history of its values at different snap points. When set is called, record the change against the current snap_id. When snap is called, just increment the snap counter -- there's nothing to copy.
The clever part comes with get. Given an index and a snap_id, we need to find what value that index had at that snapshot. The history for each index is a sorted list of (snap_id, value) pairs. We need the entry with the largest snap_id that is less than or equal to the queried snap_id. That's a classic binary search problem.
Think of it like a version control log for each cell. Instead of saving the entire spreadsheet every time, each cell remembers its own edit history. To find what a cell contained in version 5, you look through that cell's log for the most recent edit at or before version 5.
Each index independently tracks its own modification history. Since snap_ids only increase, the history list for each index is naturally sorted by snap_id. When we need to find the value at a specific snapshot, we're looking for the latest modification that happened at or before that snapshot. This is exactly what binary search on a sorted list gives us.
The critical optimization over the brute force is that snap() does zero work. Instead of copying the entire array, we just bump a counter. The cost is shifted to get(), which now does O(log S) binary search instead of O(1) lookup. But since S (the number of entries per index) is bounded by the number of set calls, and binary search is fast, this trade-off is overwhelmingly in our favor.
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). Thesnapjust increments 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.