DSA Snapshot Array

The problem: the snapshot array spec

A snapshot array is an array that can freeze its whole state at a moment and answer reads from any frozen moment later. Three operations define it. A set writes one index, a snap freezes the current state and returns a snap id, and a get reads one index as of one snap id.

Snap ids count up from zero. Every index starts at zero. A get for a snap reads the value the index held when that snap was taken.

script = [
    "set(0, 5)",
    "snap() -> 0",
    "set(0, 8)",
    "set(2, 3)",
    "snap() -> 1",
    "get(0, 0) -> 5",
    "get(0, 1) -> 8",
    "get(2, 0) -> 0",
    "get(2, 1) -> 3",
    "get(1, 1) -> 0",
]
print("array length: 3")
for line in script:
    print(line)

Index 0 changes between the two snaps, so its two reads differ. Index 2 is first set after snap 0, so its snap 0 read is the starting zero.

Intuition: copy the whole array at every snap

The first design keeps the live array and stores a full copy of it at each snap. A get then reads one cell of one copy. Reads are simple, and the copies are the cost.

The copy price is the array length, paid on every snap, even when only one index changed since the last snap. Long arrays with frequent snaps pay it in full each time.

length = 6
snaps = 4
changed_per_snap = 1
print("cells copied per snap:", length)
print("cells copied over", snaps, "snaps:", length * snaps)
print("cells that actually changed:", changed_per_snap * snaps)

Twenty-four cells are copied to record four real changes. The real design stores only the changes, one small history per index.

Brute force: the copying array, counted

The naive design is the intuition, written as a class. A counter records every cell copied across all snaps. The class runs the article script so its answers can be checked against the spec.

class CopyArray:
    def __init__(self, length):
        self.live = [0] * length
        self.copies = []
        self.cells_copied = 0

    def set(self, index, value):
        self.live[index] = value

    def snap(self):
        self.copies.append(list(self.live))
        self.cells_copied += len(self.live)
        return len(self.copies) - 1

    def get(self, index, snap_id):
        return self.copies[snap_id][index]

arr = CopyArray(3)
arr.set(0, 5)
print("snap", arr.snap())
arr.set(0, 8)
arr.set(2, 3)
print("snap", arr.snap())
print("index 0 at snap 0:", arr.get(0, 0))
print("index 0 at snap 1:", arr.get(0, 1))
print("index 2 at snap 0:", arr.get(2, 0))
print("index 2 at snap 1:", arr.get(2, 1))
print("index 1 at snap 1:", arr.get(1, 1))
print("cells copied in total:", arr.cells_copied)

Every read matches the script. Two snaps of a three-cell array already copy six cells. The count grows with length times snaps, and most copied cells carry values that never changed.

The optimal solution: one version history per index

Each index keeps its own list of version pairs, where a pair holds the snap id at which a value was set and the value itself, and a snap records only the current counter. That split is the whole design.

A set appends one pair to one index history, or rewrites the last pair when the index was already set inside the current snap period. A get binary searches one history for the last pair whose snap id is not larger than the wanted snap. That pair is called the floor pair.

import bisect

class SnapshotArray:
    def __init__(self, length):
        self.hist = [[(-1, 0)] for _ in range(length)]
        self.snap_id = 0

    def set(self, index, value):
        entry = self.hist[index]
        if entry[-1][0] == self.snap_id:
            entry[-1] = (self.snap_id, value)
        else:
            entry.append((self.snap_id, value))

    def snap(self):
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index, snap_id):
        entry = self.hist[index]
        ids = [p[0] for p in entry]
        pos = bisect.bisect_right(ids, snap_id) - 1
        return entry[pos][1]

    def history(self, index):
        return list(self.hist[index])

arr = SnapshotArray(3)
arr.set(0, 5)
print("snap", arr.snap())
arr.set(0, 8)
arr.set(2, 3)
print("snap", arr.snap())
print("index 0 at snap 0:", arr.get(0, 0))
print("index 0 at snap 1:", arr.get(0, 1))
print("index 2 at snap 0:", arr.get(2, 0))
print("index 2 at snap 1:", arr.get(2, 1))
print("index 1 at snap 1:", arr.get(1, 1))

Every read matches the script, with no array copy anywhere. Each history starts with the pair (-1, 0), which makes an unset index read as zero at every snap.

Walkthrough: the script, step by step

The walk reruns the script and prints the histories after the sets and snaps. Only the touched index grows a pair. All other histories stay untouched.

import bisect

class SnapshotArray:
    def __init__(self, length):
        self.hist = [[(-1, 0)] for _ in range(length)]
        self.snap_id = 0

    def set(self, index, value):
        entry = self.hist[index]
        if entry[-1][0] == self.snap_id:
            entry[-1] = (self.snap_id, value)
        else:
            entry.append((self.snap_id, value))

    def snap(self):
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index, snap_id):
        entry = self.hist[index]
        ids = [p[0] for p in entry]
        pos = bisect.bisect_right(ids, snap_id) - 1
        return entry[pos][1]

    def history(self, index):
        return list(self.hist[index])

arr = SnapshotArray(3)
def show(action):
    print(action, "-> histories:", [arr.history(i) for i in range(3)], "| next snap id:", arr.snap_id)

arr.set(0, 5)
show("set(0, 5)")
print("snap returns:", arr.snap())
arr.set(0, 8)
show("set(0, 8)")
arr.set(2, 3)
show("set(2, 3)")
print("snap returns:", arr.snap())
show("after snap 1")
print("get(0, 0):", arr.get(0, 0), "get(0, 1):", arr.get(0, 1))

Index 0 ends with three pairs, one for its starting zero and one per set. Index 1 keeps only its starting pair through the whole script, which is why it reads zero at every snap.

Complexity

A set touches one history entry, so its time is O(1), and a snap moves one counter, so its time is O(1) as well. A get binary searches one index history, so its time is O(log v) for v versions of that index, and the total space is O(total sets) across all histories.

for length, snaps in [(100, 50), (1000, 100)]:
    print("length", length, "snaps", snaps, "- copy design cells:", length * snaps, " history pairs at 10 sets per snap:", 10 * snaps + length)

The history column counts one starting pair per index plus one pair per set, at ten sets per snap. Sparse changes keep it far below the copy column, and dense changes are the honest worst case where the two meet.

Edge cases and pitfalls

Setting one index twice inside a single snap period keeps only the last value for that period. The earlier set never belonged to any frozen state, so storing it would waste space and could confuse the floor search.

The classic pitfall searches for an exact snap id match. Most histories skip most snap ids, so an exact search misses. The floor rule takes the last pair at or before the wanted snap, which is the value actually live then.

import bisect

class SnapshotArray:
    def __init__(self, length):
        self.hist = [[(-1, 0)] for _ in range(length)]
        self.snap_id = 0

    def set(self, index, value):
        entry = self.hist[index]
        if entry[-1][0] == self.snap_id:
            entry[-1] = (self.snap_id, value)
        else:
            entry.append((self.snap_id, value))

    def snap(self):
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index, snap_id):
        entry = self.hist[index]
        ids = [p[0] for p in entry]
        pos = bisect.bisect_right(ids, snap_id) - 1
        return entry[pos][1]

    def history(self, index):
        return list(self.hist[index])

arr = SnapshotArray(2)
arr.set(0, 5)
arr.set(0, 7)
print("history of 0 after two sets in one period:", arr.history(0))
print("snap:", arr.snap())
print("get(0, 0):", arr.get(0, 0))
print("never set index at snap 0:", arr.get(1, 0))
print("snap with no changes returns:", arr.snap())
print("get(0, 1) after an unchanged snap:", arr.get(0, 1))
arr.set(1, 4)
print("snap:", arr.snap())
print("get(1, 0):", arr.get(1, 0), "get(1, 2):", arr.get(1, 2))

The unchanged snap still returns a fresh id and reads the same values. A snap is a moment marker, not a diff, so an empty moment is a valid moment.