Snapshot Array (LeetCode 1146)

The problem

Design an array of a given length, initially all zeros, that can take snapshots:

• set(index, val): set the element at index to val;
• snap(): take a snapshot and return its id (0 for the first, then 1, 2, …);
• get(index, snap_id): return the value at index as it was when snapshot snap_id was taken.

SnapshotArray(3)
set(0, 5)
snap()     -> 0
set(0, 6)
get(0, 0)  -> 5      (snapshot 0 was taken before the 6 was written)

How to think about it

Start with brute force. On every snap(), copy the whole array and store the copy. get is then a direct lookup, O(1). But each snapshot costs O(length) time and memory. With up to 50,000 elements and 50,000 snapshots, that is billions of cells, almost all of them unchanged copies.

The key insight: store changes, not copies. Most indices don’t change between snapshots. So for each index, keep a history of (snap_id, value) pairs: one entry per set, tagged with the snapshot id that is currently being built. snap() then does no copying at all; it just increases the counter.

Answering get is a binary search. The value of index at snapshot s is the last entry in its history with snap_id ≤ s. The history is appended in increasing snap_id order, so it is sorted, and you can find that entry with bisect_right in O(log k). Seed every history with (-1, 0) so there is always an answer (the initial zero).

Which pattern is this? Design a data structure with per-key sorted history + binary search, the same idea behind time-based key-value stores and version control. The tell is “query the state as of an earlier version / time”.

Approach

1. Keep snap_id = 0 (the snapshot currently being built) and, for each index, a history list starting as [(-1, 0)].
2. set(index, val): append (snap_id, val) to that index’s history.
3. snap(): increase snap_id and return the old value.
4. get(index, s): binary-search the history for the last pair whose first element is at most s, and return its value. Searching for (s, inf) with bisect_right lands just after every pair with snap_id ≤ s, so subtract one.

Solution

import bisect

class SnapshotArray:
    def __init__(self, length):
        self.snap_id = 0; self.history = [[(-1, 0)] for _ in range(length)]   # sentinel: initial 0
    def set(self, index, val):
        self.history[index].append((self.snap_id, val))    # record change under the current snap
    def snap(self):
        self.snap_id += 1; return self.snap_id - 1          # O(1): no copying
    def get(self, index, snap_id):
        hist = self.history[index]
        i = bisect.bisect_right(hist, (snap_id, float('inf'))) - 1   # last entry with id <= snap_id
        return hist[i][1]
# set(0,5) snap()->0 set(0,6) get(0,0)->5

Dry run

The example, extended with a second write in the same snapshot and an untouched index:

For get(0, 1), two entries have id 1. Searching for (1, inf) lands after both, so the later write, 7, wins.

Complexity

• set: O(1) amortised append. snap: O(1).
• get: O(log k), where k is the number of writes to that index.
• Space: O(length + number of set calls). Nothing is copied on snap.

Edge cases and pitfalls

• Several writes in one snapshot all get the same id. Use bisect_right with (snap_id, inf) so the last write wins. Searching for (snap_id, 0) or using bisect_left can return an older value.
• Never-set index returns 0 thanks to the (-1, 0) sentinel.
• Off-by-one on the id. Writes after snap() belong to the next snapshot, which is why snap() returns snap_id - 1.
• Many writes to one index in one snapshot grow its history. An optimisation is to overwrite the last entry when its id equals the current snap_id.
• Copying the array on snap passes small tests but times out or runs out of memory on large ones.

Related problems

• Time Based Key-Value Store (LeetCode 981): the same “sorted history per key + binary search” design, keyed by timestamp.
• Search Insert Position (LeetCode 35): the bisect step on its own: where would this value go in a sorted list?
• Design Underground System (LeetCode 1396): another design that stores just enough per key to answer queries quickly.