val.

int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.

int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Examples

Example 1:

Input:
["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output:
 [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Solution

Method 1 – Per-Index Version List with Binary Search

Intuition

To efficiently support snapshots and queries, we store a history of value changes for each index, along with the snapshot id when the change occurred. This allows us to quickly retrieve the value at any index for any snapshot using binary search.

Approach

For each index, maintain a list of (snap_id, value) pairs representing changes.
On set, record the value and current snap_id for the index.
On snap, increment the gl

Related Tags