1. Snapshot Array (LeetCode)
Model answer
The task
Implement an array that supports updates, saving snapshots, and reading an index’s value as it was at a particular snapshot.
Key idea
For each index, store only the values that were explicitly set, tagged with the current snapshot ID. These IDs are ordered, so a binary search finds the most recent update no later than the requested snapshot.
Approach
- Keep a history list for each index and a counter for the next snapshot ID.
- On
set, overwrite that index’s last history entry if it belongs to the current snapshot; otherwise, append a new entry. - On
snap, return the current ID and advance the counter. - On
get, binary-search the index’s history for the last entry whose ID is at most the requested ID. - Return
0if that index has no earlier recorded update.
class SnapshotArray:
def __init__(self, length: int):
self.histories = [[] for _ in range(length)]
self.current_snap_id = 0
def set(self, index: int, val: int) -> None:
history = self.histories[index]
# Only the final value set in a snapshot needs to be recorded.
if history and history[-1][0] == self.current_snap_id:
history[-1] = (self.current_snap_id, val)
else:
history.append((self.current_snap_id, val))
def snap(self) -> int:
snap_id = self.current_snap_id
self.current_snap_id += 1
return snap_id
def get(self, index: int, snap_id: int) -> int:
history = self.histories[index]
# Find the first history entry with an ID greater than snap_id.
low, high = 0, len(history)
while low < high:
mid = (low + high) // 2
if history[mid][0] <= snap_id:
low = mid + 1
else:
high = mid
# The preceding entry is the latest update visible in this snapshot.
return history[low - 1][1] if low > 0 else 0
Complexity:
- Time:
setandsnapare O(1);getis O(log H), where H is the history length for that index. - Space: O(W), where W is the number of recorded writes across all indices.
Common follow-ups
- How can memory be reduced when values often repeat? Skip recording a set when it matches the most recent value.
- How would you support undoing snapshots? Use a persistent structure or retain version roots so earlier states remain addressable.
- What if reads are much more frequent than writes? The per-index histories already make reads efficient, with logarithmic lookup.