Implement a SnapshotArray that supports the following interface:
SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.void set(index, val) sets the element at the given index to be equal to 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
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
Constraints:
1 <= length <= 5 * 1040 <= index < length0 <= val <= 1090 <= snap_id < (the total number of times we call snap())5 * 104 calls will be made to set, snap, and get.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.
This approach involves using a dictionary to map each index to another dictionary, which maps the snapshot version to the value at that index. Each call to set(index, val) updates our dictionary for the current snapshot version. When snap() is called, it simply increments the snapshot counter and returns the previous version of the snapshot. For get(index, snap_id), we check the dictionary at that index for the most recent version less than or equal to snap_id.
The SnapshotArray is initialized with the given length, creating a list of empty dictionaries, one for each index. The current snap_id starts at 0. The set() method updates the dictionary at the given index for the current snap_id. The snap() method returns the current snap_id and then increments it. The get() method searches backwards for the closest snapshot less than or equal to snap_id that has a value set and returns it.
Time Complexity: O(1) for set() and snap(); O(n) worst-case for get(), where n is the number of snapshots.
Space Complexity: O(l + m) where l is the length of the array, and m is the number of set operations.
This approach takes advantage of a more compact representation by only storing changes using a sorted list of tuples for each index. Each tuple contains a snapshot_id and the corresponding value. This method optimizes memory usage by skipping the storage of unaltered initial values, effectively treating them as zeroes until explicitly set.
In JavaScript, we utilize an array of lists where each list is sorted by snapshot ids. The set() method either updates the last element of the list if the snapshot ids match or appends a new pair. snap() increments the snapshot id. For get(), binary search finds the largest snapshot id less than or equal to snap_id.
JavaScript
C#
Time Complexity: O(log n) for get() due to binary search; O(1) for set() and snap().
Space Complexity: O(l + m).
We maintain an array of length length. Each element in the array is a list, which is used to store the value set each time and the corresponding snapshot ID.
When the set method is called, we add the value and snapshot ID to the list at the corresponding index. The time complexity is O(1).
When the snap method is called, we first increment the snapshot ID, then return the snapshot ID minus one. The time complexity is O(1).
When the get method is called, we use binary search to find the first snapshot ID greater than snap_id at the corresponding position, and then return the previous value. If it cannot be found, return 0. The time complexity is O(log n).
The space complexity is O(n).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: HashMap of Index Changes | Time Complexity: O(1) for |
| Approach 2: Versioned Sparse Value Allocation | Time Complexity: O(log n) for |
| Array + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Full Snapshot Copy (Brute Force) | set: O(1), snap: O(n), get: O(1) | O(n × snaps) | Conceptual baseline or when array size and snapshot count are very small |
| HashMap of Index Changes | set: O(1), snap: O(1), get: O(log k) | O(m) | General case; optimal for large arrays with many snapshots but relatively few updates |
| Versioned Sparse Value Allocation | set: O(1), snap: O(1), get: O(log k) | O(m) | When implementing persistent or versioned storage patterns |
Snapshot Array || Binary Search || Design Problem || Leetcode 1146 • Aryan Mittal • 7,067 views views
Watch 9 more video solutions →Practice Snapshot Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor