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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5typedef struct Node {
6 int snap_id;
7 int value;
8 struct Node *next;
9} Node;
10
11typedef struct {
12 Node **arr;
13 int length;
14 int snap_id;
15} SnapshotArray;
16
17SnapshotArray* snapshotArrayCreate(int length) {
18 SnapshotArray* obj = (SnapshotArray*)malloc(sizeof(SnapshotArray));
19 obj->arr = (Node**)malloc(sizeof(Node*) * length);
20 obj->length = length;
21 obj->snap_id = 0;
22 for (int i = 0; i < length; i++) {
23 obj->arr[i] = (Node*)malloc(sizeof(Node));
24 obj->arr[i]->snap_id = -1;
25 obj->arr[i]->value = 0;
26 obj->arr[i]->next = NULL;
27 }
28 return obj;
29}
30
31void snapshotArraySet(SnapshotArray* obj, int index, int val) {
32 Node* node = (Node*)malloc(sizeof(Node));
33 node->snap_id = obj->snap_id;
34 node->value = val;
35 node->next = obj->arr[index];
36 obj->arr[index] = node;
37}
38
39int snapshotArraySnap(SnapshotArray* obj) {
40 return obj->snap_id++;
41}
42
43int snapshotArrayGet(SnapshotArray* obj, int index, int snap_id) {
44 Node* curr = obj->arr[index];
45 while (curr && curr->snap_id > snap_id) {
46 curr = curr->next;
47 }
48 return (curr) ? curr->value : 0;
49}
50
51void snapshotArrayFree(SnapshotArray* obj) {
52 for (int i = 0; i < obj->length; i++) {
53 Node* curr = obj->arr[i];
54 while (curr) {
55 Node* temp = curr;
56 curr = curr->next;
57 free(temp);
58 }
59 }
60 free(obj->arr);
61 free(obj);
62}Implementing in C involves handling raw pointers and dynamic memory directly. We create a linked list for each index to store its changes across snapshots. The set() function adds a new node for the current snapshot id. The snap() method simply increments the snapshot id. The get() function traverses the list to find the value at the snapshot id or nearest previous snapshot. Memory management is crucial to free allocated nodes.
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).
1using System;
2using System.Collections.Generic;
3
4public class SnapshotArray {
5 private int snapId;
private List<(int, int)>[] snapshots;
public SnapshotArray(int length) {
snapId = 0;
snapshots = new List<(int, int)>[length];
for (int i = 0; i < length; i++) {
snapshots[i] = new List<(int, int)>();
}
}
public void Set(int index, int val) {
var list = snapshots[index];
if (list.Count > 0 && list[list.Count - 1].Item1 == snapId) {
list[list.Count - 1] = (snapId, val);
} else {
list.Add((snapId, val));
}
}
public int Snap() {
return snapId++;
}
public int Get(int index, int snap_id) {
var list = snapshots[index];
int left = 0, right = list.Count;
while (left < right) {
int mid = (left + right) / 2;
if (list[mid].Item1 <= snap_id) left = mid + 1;
else right = mid;
}
return right == 0 ? 0 : list[right - 1].Item2;
}
}In C#, we create an array of lists for each index that contain tuples of (snap_id, value). The Set() method updates or appends a new snapshot-value pair. We assume all non-set values as zeros. The get() method performs a binary search on these tuples to find the required value.