Leetcode - Snapshot Array

Question

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

Idea

• Relatively simple problem but the trick here is to not overflow our memory limits.
• We cannot just maintain the entire array for every snapshot but we don’t need to since what we’re primarily concerned about is the history of our changes.
• We implement a list where each index in the list is a snap_id containing a hash map of the form {index: value}
• On get(), we start at a given snap_id and see if our index is in our hash map, searching linearly backwards O(snap_id), until, we find a value for our index, otherwise we return the default value of 0

Optimal solution

• The optimal solution uses binary search instead of just checking all indices in reverse order
• We use an array of array arrays as our data structure here self.snapshotArray = [[[0, 2], [1, 2]]] of self.snapshotArray[index][[snap_id][value]]
• The twist here is when we set, we want to make sure we overwrite the most recent value if we have the same snap_id so we don’t make multiple entries in our array self.snapshotArray[index][-1][1] = val if self.snapshotArray[index][-1][0] == snap_id
• Then in get, we can use a binary search to get our value because we are inherently sorted by our snap_id so this will be more efficient rather than scanning
• When we run binary search, we want to store the last value on updating l into res which we return if we never find the seen value

Solution

Optimal Solution

Rawdogged solution minus the binary search