{x}
blog image

Snapshot Array

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

Solution Explanation: Snapshot Array

This problem requires implementing a data structure that efficiently handles snapshots of an array. The solution uses an array of arrays to store the history of each element's value and the corresponding snapshot ID. Binary search is employed to quickly retrieve the value of an element at a specific snapshot ID.

Data Structure:

The core of the solution is a list of lists (or a similar structure depending on the language used). arr[i] stores the history of changes to the i-th element of the array. Each inner list contains pairs (snap_id, val), representing the value (val) of the element at a particular snapshot ID (snap_id).

Methods:

  • __init__(length) (Constructor): Initializes the array of lists with the specified length. Each inner list is initially empty, effectively representing an array of zeros.

  • set(index, val): Appends the current snapshot ID (self.i) and the new value (val) to the history list for the given index. This efficiently updates the array.

  • snap(): Increments the global snapshot ID (self.i) and returns the previous snapshot ID. This creates a new snapshot point in time.

  • get(index, snap_id): This is where the binary search comes into play. It searches within the history list at arr[index] to find the largest snap_id less than or equal to the given snap_id. The corresponding value is then returned. If no such snap_id is found (the element was never set before the requested snapshot), it returns 0 (as per the problem's default value).

Time Complexity Analysis:

  • __init__(length): O(length) - Creating an array of length length.
  • set(index, val): O(1) - Appending to a list is a constant-time operation.
  • snap(): O(1) - Simple increment and return.
  • get(index, snap_id): O(log m), where 'm' is the number of snapshots taken for the specific element. This is due to the binary search performed within the history list of that element. In the worst case (many updates to a single element), this can approach O(log N), where N is the total number of set operations across all elements.

Space Complexity Analysis:

The space complexity is O(Nm), where N is the length of the array and m is the average number of snapshots taken per element. This is because we are storing the history of changes for each element. In the worst case, where every element is updated in every snapshot, this approaches O(NS), where S is the total number of snap operations.

Example in Python:

The Python code leverages the bisect_left function from the bisect module for efficient binary search. The inf (infinity) is used as a placeholder to ensure that the binary search always finds a valid position.

The provided code snippets in various languages (Python, Java, C++, Go, and TypeScript) all follow this same fundamental approach, differing only in syntax and the specific libraries used for the binary search or array manipulation. They all have the same time and space complexity characteristics as described above.