Take snapshots of a huge array cheaply: each index keeps only its changes, and a binary search finds the value at any snap id.
▼The problem
LeetCode 1146 (Medium). Implement SnapshotArray(length): an array of length zeros with set(index, val), snap() (takes a snapshot and returns its snap_id, the number of snaps taken minus 1) and get(index, snap_id) (the value at index when snap snap_id was taken).
Example (LeetCode's, scene 2): SnapshotArray(3), set(0, 5), snap() → 0, set(0, 6), get(0, 0) → 5.
The solution
from bisect import bisect_right
from math import inf
class SnapshotArray:
def __init__(self, length):
self.snap_id = 0
self.hist = [[(-1, 0)] for _ in range(length)]
def set(self, index, val):
h = self.hist[index]
if h[-1][0] == self.snap_id:
h[-1] = (self.snap_id, val)
else:
h.append((self.snap_id, val))
def snap(self):
self.snap_id += 1
return self.snap_id - 1
def get(self, index, snap_id):
h = self.hist[index]
i = bisect_right(h, (snap_id, inf)) - 1
return h[i][1]Transcript
Snapshot Array. Build an array of zeros that supports three moves: set an index to a value; snap, which saves the array and returns a snap id; and get, which reads an index as it was at a given snap.
LeetCode's example has length three. Set index zero to five. Snap returns zero. Set index zero to six. Get index zero at snap zero: five, not six.
The naive way copies the whole array on every snap. That's order n per snap; fifty thousand slots and fifty thousand snaps store two and a half billion values, mostly repeats.
Better: log changes, not copies. Each index keeps a history of snap id and value pairs, starting with a zero. Set appends a pair, or overwrites the last one if its snap id matches. Snap just bumps a counter. Get binary searches that history for the last pair at or before the snap id.
In code, set touches one list, snap is one line, and get is bisect right minus one.
Now a longer, illustrative session. Index one gets four, then snap zero. Seven, then snaps one and two. Two, overwritten by nine, then snap three. Five, then snap four. Get index one at snap two. The middle pair, snap one, is early enough: go right. Snap four is too late: go left. Snap three, too late. The answer is seven.
Set and snap are order one, get is order log of the history length, and space grows with the sets, not the snaps.
Log the changes, count the snaps, search the history. That's Snapshot Array.