Snapshot Array

Med

#1079Time: - **Constructor**: O(L) to initialize the array. - **`set`**: O(1). - **`snap`**: O(L) due to the array copying. - **`get`**: O(1) for HashMap lookup.Space: O(S * L), where S is the number of snapshots and L is the array length. This is because for each of S snapshots, we store a full copy of the array of length L.7 companies

Patterns

Design

Algorithms

Binary Search

Data structures

Array Hash Table

Companies

Nvidia Snowflake Coupang Databricks

Prompt

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 * 10⁴
0 <= index < length
0 <= val <= 10⁹
0 <= snap_id < (the total number of times we call snap())
At most 5 * 10⁴ calls will be made to set, snap, and get.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is the most straightforward and intuitive. We maintain a current version of the array. Every time snap() is called, we create a complete, deep copy of the current array and store it in a map, using the snap_id as the key. This ensures that we have a perfect record of the array's state for each snapshot.

Algorithm

Initialize current_array of size length, a HashMap<Integer, int[]> snapshots, and snap_id = 0.
set(index, val): Update current_array[index] = val.
snap():
1. Create a copy: int[] copy = Arrays.copyOf(current_array, length).
2. Store the copy: snapshots.put(snap_id, copy).
3. Return snap_id++.
get(index, snap_id):
1. Retrieve the snapshot: int[] snapshot_array = snapshots.get(snap_id).
2. Return snapshot_array[index].

Walkthrough

In this method, we use a simple integer array, let's call it current_array, to store the most recent state of the data. A HashMap<Integer, int[]> named snapshots is used to store the historical versions of the array, where the key is the snap_id and the value is the array state at that snapshot. A counter snap_id tracks the number of snapshots taken.

SnapshotArray(length): Initializes current_array of the given length with zeros, initializes the snapshots map, and sets snap_id to 0.
set(index, val): Updates the value in current_array at the given index. This is a constant time operation.
snap(): This is the core of this approach. It creates a deep copy of current_array and stores it in the snapshots map with the current snap_id. It then increments snap_id and returns the ID of the snapshot just created. The copy operation takes time proportional to the length of the array.
get(index, snap_id): Retrieves the array corresponding to the given snap_id from the snapshots map and then returns the element at the specified index.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class SnapshotArray {6    private int[] current_array;7    private Map<Integer, int[]> snapshots;8    private int snap_id;9 10    public SnapshotArray(int length) {11        current_array = new int[length];12        snapshots = new HashMap<>();13        snap_id = 0;14    }15 16    public void set(int index, int val) {17        current_array[index] = val;18    }19 20    public int snap() {21        int[] copy = Arrays.copyOf(current_array, current_array.length);22        snapshots.put(snap_id, copy);23        return snap_id++;24    }25 26    public int get(int index, int snap_id) {27        int[] snapshot_array = snapshots.get(snap_id);28        return snapshot_array[index];29    }30}

Complexity

Time

- **Constructor**: O(L) to initialize the array. - **`set`**: O(1). - **`snap`**: O(L) due to the array copying. - **`get`**: O(1) for HashMap lookup.

Space

O(S * L), where S is the number of snapshots and L is the array length. This is because for each of S snapshots, we store a full copy of the array of length L.

Trade-offs

Pros

Simple to understand and implement.
set and get operations are very fast (O(1)).

Cons

snap() operation is slow, with a time complexity of O(L), where L is the length of the array.
Extremely high space complexity (O(S * L), where S is the number of snapshots), making it infeasible for large inputs.

This approach optimizes space and time by avoiding full array copies. Instead of storing the entire array for each snapshot, we only record the changes made to each element. For each index in the array, we maintain a history of its values, mapping the snap_id at which a value was set to the value itself. This is a 'copy-on-write' strategy applied at the element level rather than the array level.

Algorithm

Initialize history, an array of TreeMap<Integer, Integer> of size length.
For each index i, initialize history[i] and add an initial entry: history[i].put(0, 0).
Initialize snap_id = 0.
set(index, val): Record the change: history[index].put(snap_id, val).
snap(): Increment and return the snap ID: return snap_id++.
get(index, snap_id):
1. Find the relevant history entry using binary search: Map.Entry<Integer, Integer> entry = history[index].floorEntry(snap_id).
2. Return the value from the entry: return entry.getValue().

Walkthrough

The primary data structure is an array of TreeMaps, let's say history = new TreeMap[length]. Each history[i] will store the value history for the element at index i. A TreeMap is chosen because it keeps entries sorted by key (snap_id) and provides an efficient way (floorEntry) to find the relevant value for a given snapshot.

SnapshotArray(length): Initializes the history array. For each index i, a new TreeMap is created. To handle the initial state where all values are 0, we add an entry (0, 0) to each TreeMap. This signifies that at snap_id 0 (and before any set calls), the value is 0.
set(index, val): When a value is set at a particular index, we record this change in the corresponding TreeMap. We add or update the entry for the current snap_id: history[index].put(snap_id, val). This operation takes logarithmic time relative to the number of changes for that index.
snap(): This operation becomes extremely efficient. We simply increment the snap_id counter and return its previous value. No data copying is needed. This is a constant time operation.
get(index, snap_id): To get the value of an element at a specific snapshot, we look into its history TreeMap, history[index]. We need to find the value that was set at or before the requested snap_id. The TreeMap.floorEntry(snap_id) method is perfect for this; it finds the entry with the greatest key (snap_id) that is less than or equal to the given snap_id. We then return the value from this entry. Because we pre-populated the TreeMap with (0, 0), floorEntry will always find a valid entry for any non-negative snap_id.

An alternative to TreeMap is using a List of pairs (snap_id, value) for each index. Since set calls for an index will have increasing snap_ids, the list will be sorted. get can then use binary search on this list. The performance characteristics are nearly identical.

1import java.util.TreeMap;2 3class SnapshotArray {4    private TreeMap<Integer, Integer>[] history;5    private int snap_id;6 7    public SnapshotArray(int length) {8        history = new TreeMap[length];9        for (int i = 0; i < length; i++) {10            history[i] = new TreeMap<>();11            history[i].put(0, 0); // Initial value at snap_id 0 is 012        }13        snap_id = 0;14    }15 16    public void set(int index, int val) {17        history[index].put(snap_id, val);18    }19 20    public int snap() {21        return snap_id++;22    }23 24    public int get(int index, int snap_id) {25        // Find the value at the greatest snap_id <= the given snap_id26        return history[index].floorEntry(snap_id).getValue();27    }28}

Complexity

Time

- **Constructor**: O(L) to initialize the array of TreeMaps. - **`set`**: O(log K), where K is the number of times `set` has been called for that specific index. - **`snap`**: O(1). - **`get`**: O(log K), where K is the number of historical entries for that index, due to the binary search nature of `TreeMap.floorEntry`.

Space

O(C_set), where `C_set` is the total number of calls to `set`. We only store the values that are explicitly set, not full arrays.

Trade-offs

Pros

Highly efficient snap() operation (O(1)).
Massively reduced space complexity compared to the brute-force approach.
set and get are still very fast (logarithmic time).

Cons

Slightly more complex to implement and reason about than the brute-force approach.
set and get are not O(1), but O(log K), though this is negligible in practice.

Solutions

Solution

1class SnapshotArray { private List < int []>[] arr ; private int idx ; public SnapshotArray ( int length ) { arr = new List [ length ]; Arrays . setAll ( arr , k -> new ArrayList <>()); } public void set ( int index , int val ) { arr [ index ]. add ( new int [] { idx , val }); } public int snap () { return idx ++; } public int get ( int index , int snap_id ) { var vals = arr [ index ]; int left = 0 , right = vals . size (); while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( vals . get ( mid )[ 0 ] > snap_id ) { right = mid ; } else { left = mid + 1 ; } } return left == 0 ? 0 : vals . get ( left - 1 )[ 1 ]; } } /** * Your SnapshotArray object will be instantiated and called as such: * SnapshotArray obj = new SnapshotArray(length); * obj.set(index,val); * int param_2 = obj.snap(); * int param_3 = obj.get(index,snap_id); */

1class SnapshotArray { public: SnapshotArray ( int length ) { idx = 0 ; arr = vector < vector < pair < int , int >>> ( length ); } void set ( int index , int val ) { arr [ index ]. push_back ({ idx , val }); } int snap () { return idx ++ ; } int get ( int index , int snap_id ) { auto & vals = arr [ index ]; int left = 0 , right = vals . size (); while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( vals [ mid ]. first > snap_id ) { right = mid ; } else { left = mid + 1 ; } } return left == 0 ? 0 : vals [ left - 1 ]. second ; } private: vector < vector < pair < int , int >>> arr ; int idx ; }; /** * Your SnapshotArray object will be instantiated and called as such: * SnapshotArray* obj = new SnapshotArray(length); * obj->set(index,val); * int param_2 = obj->snap(); * int param_3 = obj->get(index,snap_id); */

1class SnapshotArray : def __init__ ( self , length : int ): self . idx = 0 self . arr = defaultdict ( list ) def set ( self , index : int , val : int ) -> None : self . arr [ index ]. append (( self . idx , val )) def snap ( self ) -> int : self . idx += 1 return self . idx - 1 def get ( self , index : int , snap_id : int ) -> int : vals = self . arr [ index ] i = bisect_right ( vals , ( snap_id , inf )) - 1 return 0 if i < 0 else vals [ i ][ 1 ] # Your SnapshotArray object will be instantiated and called as such: # obj = SnapshotArray(length) # obj.set(index,val) # param_2 = obj.snap() # param_3 = obj.get(index,snap_id)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem