snapshot-array-notes

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.

Made on mmm