[1146. Snapshot Array]
[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 givenindex
to 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
class SnapshotArray:
def __init__(self, length: int):
self.snap_id = -1
self.collections = [[[self.snap_id, 0]] for _ in range(length)]
self.length = length
def set(self, index: int, val: int) -> None:
if self.snap_id == self.collections[index][-1][0]:
self.collections[index][-1][1] = val
else:
self.collections[index].append([self.snap_id, val])
def snap(self) -> int:
self.snap_id += 1
return self.snap_id
def get(self, index: int, snap_id: int) -> int:
i = bisect.bisect_right(self.collections[index], [snap_id, float('-inf')]) - 1
return self.collections[index][i][1]