Snapshot Array

Keep the live array plus a list of full copies. set mutates the live array in place. snap appends a copy of the live array and returns its new index. get indexes straight into the stored copy. Every answer is trivially correct, because each stored snapshot really is a frozen array.

class SnapshotArray:
    def __init__(self, length: int):
        self.array = [0] * length
        self.snapshots = []

    def set(self, index: int, val: int) -> None:
        self.array[index] = val

    def snap(self) -> int:
        self.snapshots.append(self.array[:])
        return len(self.snapshots) - 1

    def get(self, index: int, snap_id: int) -> int:
        return self.snapshots[snap_id][index]

Why it is too slow: set and get are O(1), but every snap pays O(length) time and O(length) space — it duplicates the entire array. With length up to 5 * 10^4 and up to 5 * 10^4 snapshot calls, that is up to 2.5 * 10^9 element copies and the same order of stored values. The cost is paid on every snapshot even when only one index ever changes, which is exactly the waste the optimal solution removes.

Never copy the array. Give each index its own log of (snap_id, value) pairs, appended only when that index changes. Because snap merely increments a counter, a write is tagged with the snap id current at write time, and snap ids only ever increase — so each log is automatically sorted by id. To answer get(index, snap_id) we need the value that was live at that snapshot, which is the last pair with id at most snap_id. Binary search finds the first pair with id greater than snap_id; the answer is the pair immediately before it, or 0 when no pair qualifies (the index was never written before that snapshot).

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

    def set(self, index: int, val: int) -> None:
        self.history[index].append((self.snap_id, val))

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

    def get(self, index: int, snap_id: int) -> int:
        versions = self.history[index]
        lo, hi = 0, len(versions)
        # Find the first entry whose snap id is greater than the requested id.
        while lo < hi:
            mid = (lo + hi) // 2
            if versions[mid][0] > snap_id:
                hi = mid
            else:
                lo = mid + 1
        # The answer is the entry just before that insertion point.
        return 0 if lo == 0 else versions[lo - 1][1]

Why it works: a value is live at snapshot s exactly from the moment its write is stamped s until a later write to the same index is stamped a larger id. So the value at snapshot s is simply the most recent write with id at most s — no other state is involved. Logs are sorted, so “most recent write with id at most s” is one binary search. Index 0 in the file example shows the whole story: after set(0, 5), snap(), and set(0, 6), index 0 holds [(0, 5), (1, 6)]; get(0, 0) returns 5 because the first id greater than 0 is 1, and the pair before it is (0, 5).

Watch one index log grow, then watch get(0, 0) binary-search it: the window [lo, hi) shrinks until lo marks the first entry newer than snapshot 0, and the answer is the entry just before it.

Why it is fast: set is a single append, O(1). snap increments an integer, O(1). get binary-searches one index log, O(log k) where k is the number of writes to that index (at most the total number of set calls). Nothing is ever copied, so total space is O(length) for the logs plus one pair per set call — O(n + s) where s is the number of writes. Contrast that with the brute force, which stores length × snapshots values regardless of how few indices actually changed.