The machine is a length-n array where set(index, value) writes a value, snap() freezes the entire array and returns a snapshot id, and get(index, snap_id) must read the value that index held when that snapshot was taken. Snapshots never change, and the array may be mutated arbitrarily between them.
The copy-on-write trick is that a snapshot does not copy anything. Instead of a 2D array of snapshots × indices — O(n × s) memory — the machine keeps, per index, a list of (snap_id, value) pairs recording only the writes that touched that index. snap() merely increments a global counter and returns it. A set records (current_snap, value) at that index, replacing the previous entry for the same snap (same index and same snap id means overwrite, not append). A get binary-searches the index's list for the rightmost pair with snap_id ≤ the requested id and returns its value, or 0 if no such pair exists.
Complexity: set is O(1) amortized (one append or overwrite), snap is O(1) — just an integer increment — and get is O(log k) where k is the number of writes ever made to that index, via bisect on the snap ids. Total memory is O(total writes), not O(n × snaps). This is the same pattern versioned databases use for MVCC: history per row, not full copies per transaction.
Edge cases: a snap id predating any write to the index returns 0; multiple consecutive snaps with no writes between them answer the same value because the search is for the rightmost pair ≤ id; overwriting an index twice inside one snap id must not create duplicate entries, or the bisect breaks.
from bisect import bisect_right
class SnapshotArray:
def __init__(self, length):
self.history = [[(-1, 0)] for _ in range(length)]
self.snap_id = 0
def set(self, index, val):
h = self.history[index]
if h[-1][0] == self.snap_id:
h[-1] = (self.snap_id, val) # overwrite same snapshot
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.history[index]
i = bisect_right(h, (snap_id, float('inf'))) - 1
return h[i][1]