Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Snapshot Array
Bookmark
Input
Standard
Multiple Snaps
Sparse
Custom
length
=
3
,
operations
=
[set(0,5), snap(), set(0,6), get(0,0), set(1,10), snap(), get(0,1), get(1,1)]
snapCount =
0
[0]
0
s0
0
[1]
0
s0
0
[2]
0
s0
0
snapCount =
0
[0]
0
s0
0
[1]
0
s0
0
[2]
0
s0
0
set(0, 5)
snapCount =
0
[0]
0
s0
5
[1]
0
s0
0
[2]
0
s0
0
same snap
, overwrite in place: (
0
,
5
)
set(0, 6)
snapCount =
1
snaps
s0
[0]
0
1
s0
5
s1
6
[1]
0
s0
0
[2]
0
s0
0
older snap
, append: history[0] += (
1
,
6
)
get(0, 0)
snapCount =
1
snaps
s0
[0]
0
1
s0
5
s1
6
lo
hi
mid
[1]
0
s0
0
[2]
0
s0
0
mid = 0 + (1 - 0 + 1) / 2 =
1
snap_id[1] =
1
<=
0
?
get(0, 0)
snapCount =
1
snaps
s0
[0]
0
1
s0
5
s1
6
snap 0
[1]
0
s0
0
[2]
0
s0
0
return
5
snap()
snapCount =
2
snaps
s0
s1
[0]
0
1
s0
5
s1
6
[1]
0
1
s0
0
s1
10
[2]
0
s0
0
return
1
snapCount = 1 + 1 =
2
get(0, 1)
snapCount =
2
snaps
s0
s1
[0]
0
1
s0
5
s1
6
lo
hi
mid
[1]
0
1
s0
0
s1
10
[2]
0
s0
0
mid = 0 + (1 - 0 + 1) / 2 =
1
snap_id[1] =
1
<=
1
?
get(0, 1)
snapCount =
2
snaps
s0
s1
[0]
0
1
s0
5
s1
6
snap 1
[1]
0
1
s0
0
s1
10
[2]
0
s0
0
return
6
get(1, 1)
snapCount =
2
snaps
s0
s1
[0]
0
1
s0
5
s1
6
[1]
0
1
s0
0
s1
10
lo
hi
mid
[2]
0
s0
0
1 <= 1
keep mid, lo =
1
snapCount =
2
snaps
s0
s1
[0]
0
1
s0
5
s1
6
[1]
0
1
s0
0
s1
10
[2]
0
s0
0
done,
2
snapshots taken
algo
master
.
io
Step:
Start: a SnapshotArray of length 3. Each index stores a history of (snap_id, value) pairs, starting as (0, 0). snapCount = 0.
0 / 21
Input
Standard
Multiple Snaps
Sparse
Custom
length
=
3
,
operations
=
[set(0,5), snap(), set(0,6), get(0,0), set(1,10), snap(), get(0,1), get(1,1)]
0 / 21
algo
master
.
io
Step:
Start: a SnapshotArray of length 3. Each index stores a history of (snap_id, value) pairs, starting as (0, 0). snapCount = 0.