Snapshot Array

Medium

Asked by:

+10

38 views

Topics:

ArraysBinary Search

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.

Snapshot Array

Medium

Asked by:

+4

38 views

Topics:

ArraysBinary Search

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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the initial array and the number of set/snap/get operations?
What is the range of possible values that can be stored in the array?
If I call `get` with a `snap_id` that doesn't exist, or an `index` that is out of bounds, what should I return or how should I handle the error?
Are the `snap_id` values guaranteed to be monotonically increasing, or can they be arbitrary non-negative integers?
What should be the initial value of elements in the array when the `SnapshotArray` is initialized (e.g., 0, null, undefined)?

Brute Force Solution

Approach

The snapshot array problem requires us to track the history of an array's values. A brute force method involves making a complete copy of the array every time we take a snapshot, storing each version separately.

Here's how the algorithm would work step-by-step:

Whenever we want to set a value at a specific spot in the array, we simply update that spot.
When we need to take a snapshot, we create an entirely new copy of the current array.
We store this entire copy along with a snapshot number, essentially preserving the entire state of the array at that point in time.
When we need to retrieve the value at a specific spot from a past snapshot, we go through our stored snapshots.
We find the last snapshot that happened *before* or exactly at the snapshot number we're asking about.
Once we find that snapshot, we look up the value at the specified spot in *that* snapshot's copy of the array.

Code Implementation

class SnapshotArray:

    def __init__(self, array_length):
        self.array = [0] * array_length
        self.snapshots = {0: self.array[:]}
        self.current_snapshot_id = 0

    def set(self, index, value):
        self.array[index] = value

    def snap(self):
        # Save a copy of the current array state
        self.current_snapshot_id += 1
        self.snapshots[self.current_snapshot_id] = self.array[:]

        return self.current_snapshot_id - 1

    def get(self, index, snapshot_id):
        # Find the correct snapshot to retrieve from
        while snapshot_id not in self.snapshots and snapshot_id > 0:
            snapshot_id -= 1

        # If snapshot doesn't exist, return 0.
        if snapshot_id not in self.snapshots:
            return 0

        # Access value from the correct snapshot
        return self.snapshots[snapshot_id][index]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The set operation takes O(1) time as it directly updates an element in the array. The snap operation takes O(n) time because it creates a copy of the entire array of size n. The get operation requires iterating through the snapshots to find the last snapshot taken before or at the given snap_id. In the worst-case scenario, we iterate through all snapshots, but since each snapshot contains n elements that doesn't affect the overall get operation which only needs to find the correct snapshot to get a single value from so it's still O(n) when there are n snapshots.

Space Complexity

O(N*S) – The described solution involves creating a complete copy of the array every time a snapshot is taken. In the worst-case scenario, we might take 'S' snapshots, each requiring storage for 'N' elements, where N is the size of the original array. Thus, the auxiliary space used grows linearly with the number of snapshots and the size of the array. The space required to store all the snapshots is therefore N*S. This leads to a space complexity of O(N*S).

Optimal Solution

Approach

The key idea is to avoid storing the entire array at each snapshot. Instead, we only store what's changed since the last snapshot, saving a lot of space and time. Think of it like version control for an array.

Here's how the algorithm would work step-by-step:

For each position in the array, keep a history of its values and the snapshot ID when it was last updated.
When you set a value at a position, record the new value and the current snapshot ID in that position's history.
When you want to get the value at a position for a specific snapshot, look back through its history to find the most recent value that was set before or during that snapshot.
Because each position only stores the changes it experiences, snapshots become very efficient, especially if only small parts of the array are changing over time.

Code Implementation

class SnapshotArray:

    def __init__(self, array_length):
        self.array_length = array_length
        self.history = [{} for _ in range(array_length)]
        self.current_snapshot_id = 0

    def set(self, index, value):
        # Store changes with the current snapshot ID
        self.history[index][self.current_snapshot_id] = value

    def snap(self):
        self.current_snapshot_id += 1
        return self.current_snapshot_id - 1

    def get(self, index, snapshot_id):
        # Find the most recent value set before or during snapshot_id
        for snap_id in reversed(sorted(self.history[index].keys())):

            if snap_id <= snapshot_id:
                #Return the value if snapshot id is before target
                return self.history[index][snap_id]

        # If no value was set before snapshot_id, return 0.
        return 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log(snap_id)) – The set operation takes O(1) as it only involves updating a list at a specific index. However, the get operation, which is crucial for understanding the overall complexity, involves searching the history of a given index. Since the history is stored as a sorted list of snapshot IDs and values, we can use binary search to find the most recent value set before or during the given snap_id. Therefore, the get operation has a time complexity of O(log(snap_id)), where snap_id represents the number of snapshots taken.

Space Complexity

O(Q) – The space complexity is determined by the number of updates performed on the array. For each index in the array, we store a history of its values along with the snapshot ID. In the worst-case scenario, every set operation modifies a distinct index for every snapshot, leading to a history entry for each set operation. Therefore, the space used grows linearly with the number of set operations or queries (Q), where Q is the number of set operations performed. Thus, the auxiliary space required is O(Q).

Edge Cases

Case	How to Handle
Initializing SnapshotArray with size 0	The array is initialized with size 0, so all set operations become no-ops and get operations should return 0.
Calling snap() many times consecutively	The snap_id counter should increment correctly and not overflow within reasonable limits, allocating new snapshot IDs as expected.
Setting a value multiple times at the same index before a snap()	Only the last set value should be considered when a snap() is called.
Getting a value from a snapshot that doesn't exist	Return 0 if the snapshot id does not exist, as this is the initial default value.
Setting negative values in the array	The set function should handle negative values correctly, storing them without any issues.
Setting and getting values close to the integer limits	Ensure that operations don't cause integer overflows during set/get operations.
Calling set with an index out of bounds	The set operation should either throw an exception or be ignored, or update array size if it increases the bound (less preferred).
Memory usage with a very large number of snapshots	Consider using a more space-efficient data structure for storing snapshots if memory becomes a bottleneck, such as a persistent data structure or only storing differences (deltas) between snapshots.