Snapshot Array - Video Solutions

Problem Overview: Design a data structure that behaves like an array but supports versioning. You must implement set(index, val), snap(), and get(index, snap_id). Each snapshot freezes the current state of the array, and later queries must return the value at a specific index when that snapshot was taken.

Approach 1: HashMap of Index Changes (set: O(1), snap: O(1), get: O(log k))

Instead of copying the entire array for every snapshot, store only the changes. For each index, maintain a list of pairs (snap_id, value). When you call set(), append the current snapshot id and value for that index. The snap() operation simply increments a global snapshot counter and returns the previous id. When get(index, snap_id) is called, perform binary search on the stored history for that index to find the most recent value whose snapshot id is ≤ the requested one. This design avoids full array duplication and keeps storage proportional to the number of updates. Time complexity is O(1) for updates, O(1) for snapshots, and O(log k) for queries where k is the number of updates to that index. Space complexity is O(m) where m is the total number of set operations. The approach combines ideas from hash tables and binary search to efficiently retrieve historical values.

Approach 2: Versioned Sparse Value Allocation (set: O(1), snap: O(1), get: O(log k))

This design treats each index as a sparse timeline of values. Instead of a generic map structure, maintain an array where each position holds a list of versioned values. Each entry records the snapshot id when a value became active. On set(), append a new version entry only if the value changes during the current snapshot window. The snap() call advances the version counter without copying any data. During get(), perform binary search over the stored versions for that index to locate the value associated with the nearest snapshot ≤ the requested id. Because most indices change infrequently, the structure stays compact. Space usage grows only with actual modifications rather than array size multiplied by snapshots. This approach is common in persistent data structures and versioned storage systems. It relies on efficient indexing using an array combined with binary search over version history.

Recommended for interviews: The HashMap-of-changes approach is the one most interviewers expect. It shows that you recognize the inefficiency of copying the entire array on every snapshot and instead store only the deltas. Mentioning binary search for efficient historical lookup demonstrates strong understanding of time–space tradeoffs. A brute-force full-copy design works conceptually but uses O(n × snaps) space, while the optimized approach scales with the number of updates instead.