## Algorithm

Problem Name: 1146. 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`.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class SnapshotArray {
TreeMap[] A;
int snapId;
public SnapshotArray(int length) {
A = new TreeMap[length];
snapId = 0;
for (int i = 0; i  <  length; i++) {
A[i] = new TreeMap();
A[i].put(0, 0);
}
}

public void set(int index, int val) {
A[index].put(snapId, val);
}

public int snap() {
return snapId++;
}

public int get(int index, int snap_id) {
return A[index].floorEntry(snap_id).getValue();
}
}
``````
Copy The Code &

Input

cmd
["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]]

Output

cmd
[null,null,0,null,5]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const SnapshotArray = function(length) {
this.snaps = Array(length)
this.snapId = 0
};

SnapshotArray.prototype.set = function(index, val) {
if(this.snaps[index] == null) {
this.snaps[index] = {}
}
this.snaps[index][this.snapId] = val
};

SnapshotArray.prototype.snap = function() {
return this.snapId++
};

SnapshotArray.prototype.get = function(index, snap_id) {
let res = 0
let id = snap_id
while(id >= 0) {
if(this.snaps[index] == null || this.snaps[index][id] == null) id--
else {
res = this.snaps[index][id]
break
}
}

return res
};
``````
Copy The Code &

Input

cmd
["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]]

Output

cmd
[null,null,0,null,5]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````start coding...
class SnapshotArray:

def __init__(self, length: int):
self.s = 0
self.arr = [[[0, 0]] for i in range(length)]

def set(self, index: int, val: int) -> None:
if self.s == self.arr[index][-1][0]:
self.arr[index][-1][1] = val
else:
self.arr[index].append([self.s, val])

def snap(self) -> int:
self.s += 1
return self.s - 1

def get(self, index: int, snap_id: int) -> int:
i = bisect.bisect_left(self.arr[index], [snap_id])
if i < len(self.arr[index]):
if self.arr[index][i][0] > snap_id:
i -= 1
return self.arr[index][i][1]
return self.arr[index][-1][1]
``````
Copy The Code &

Input

cmd
["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]]

Output

cmd
[null,null,0,null,5]