Snapshot Array
Problem Description
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 givenindexto be equal toval.int snap()takes a snapshot of the array and returns thesnap_id: the total number of times we calledsnap()minus1.int get(index, snap_id)returns the value at the givenindex, at the time we took the snapshot with the givensnap_id
Example 1:
Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
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.
Solve it on LeetCode
Approaches
1. Naive Approach
Intuition:
The naive approach involves storing the entire array for each snapshot. Although this method is simple to implement, it is not efficient as it uses a lot of memory space if the array or the number of snapshots is large.
Code:
Complexity Analysis
- Time Complexity:
set: O(1), because setting the value takes constant time.snap: O(n), where n is the length of the array, since we need to duplicate the array.get: O(1), as we directly fetch the value from a stored snapshot.- Space Complexity: O(n), due to the use of additional array.
2. Efficient Approach with Binary Search
Intuition:
Instead of storing the entire array for each snapshot, we only store the changes made for each snapshot. This can be efficiently handled using a list of TreeMaps where the keys are indices of the array, and the values are another TreeMap that maps the snapshot id to the values that were set during that snapshot.
Code:
Complexity Analysis
- Time Complexity:
set: O(log S), where S is the number of snapshots taken, for the insertion in the TreeMap.snap: O(1), as we only increment a counter.get: O(log S), due to the binary search operationfloorEntry()in TreeMap.- Space Complexity: O(n + q), where n is the length of the array and q is the number of set operations until last snap.