Sponsored
Sponsored
This approach involves using a dictionary to map each index to another dictionary, which maps the snapshot version to the value at that index. Each call to set(index, val) updates our dictionary for the current snapshot version. When snap() is called, it simply increments the snapshot counter and returns the previous version of the snapshot. For get(index, snap_id), we check the dictionary at that index for the most recent version less than or equal to snap_id.
Time Complexity: O(1) for set() and snap(); O(n) worst-case for get(), where n is the number of snapshots.
Space Complexity: O(l + m) where l is the length of the array, and m is the number of set operations.
1import java.util.*;
2
3class SnapshotArray {
4 private int snapId = 0;
5 private List<TreeMap<Integer, Integer>> arr;
6
7 public SnapshotArray(int length) {
8 arr = new ArrayList<>(length);
9 for (int i = 0; i < length; i++) {
10 arr.add(new TreeMap<>());
11 }
12 }
13
14 public void set(int index, int val) {
15 arr.get(index).put(snapId, val);
16 }
17
18 public int snap() {
19 return snapId++;
20 }
21
22 public int get(int index, int snap_id) {
23 TreeMap<Integer, Integer> snapMap = arr.get(index);
24 Map.Entry<Integer, Integer> entry = snapMap.floorEntry(snap_id);
25 return entry != null ? entry.getValue() : 0;
26 }
27}We use an ArrayList of TreeMaps to track changes. The TreeMap stores snapshot ids as keys and values as values. The set() method associates the current snapId with val for a given index. The snap() increments and returns snapId. The get() method finds the value for the largest snapshot using floorEntry(). If there's no entry, it returns 0.
This approach takes advantage of a more compact representation by only storing changes using a sorted list of tuples for each index. Each tuple contains a snapshot_id and the corresponding value. This method optimizes memory usage by skipping the storage of unaltered initial values, effectively treating them as zeroes until explicitly set.
Time Complexity: O(log n) for get() due to binary search; O(1) for set() and snap().
Space Complexity: O(l + m).
1class SnapshotArray {
2 constructor(
In JavaScript, we utilize an array of lists where each list is sorted by snapshot ids. The set() method either updates the last element of the list if the snapshot ids match or appends a new pair. snap() increments the snapshot id. For get(), binary search finds the largest snapshot id less than or equal to snap_id.