Snapshot Array: Binary Search on Per-Index History
Snapshot Array (LeetCode 1146) asks for set(index, val), snap() and get(index, snap_id). Copying the whole array on every snap is the trap; interviewers want you to store only changes.
Store history per index
Keep, for every index, a list of (snap_id, value) pairs. set() writes to the current snap id, overwriting the last pair if it has the same snap id. snap() just increments a counter and returns the old value.
get with binary search
For get(index, snap_id), binary search the index's history for the last pair whose snap_id is at most the requested one. Python's bisect makes this short.
import bisect
class SnapshotArray:
def __init__(self, length):
self.h = [[(-1, 0)] for _ in range(length)]
self.snap_id = 0
def set(self, index, val):
if self.h[index][-1][0] == self.snap_id:
self.h[index][-1] = (self.snap_id, val)
else:
self.h[index].append((self.snap_id, val))
def snap(self):
self.snap_id += 1
return self.snap_id - 1
def get(self, index, snap_id):
i = bisect.bisect_right(self.h[index], (snap_id, float('inf'))) - 1
return self.h[index][i][1]
Complexity
set and snap are O(1), get is O(log S) where S is the number of changes to that index, and memory is proportional to the number of set calls, not length times snaps.
How to talk about it
Connect it to real systems: this is the same idea as MVCC in databases and versioned key-value stores. That one sentence often turns a medium question into a strong signal.
Disclosure: I work on Linkjob AI, an interview copilot app for real-time interview practice.