Snapshot Array

Table of Contents +

This question is about saving versions. You change an array, save a snapshot, change it more, and later ask what a slot looked like back then. The naive answer copies the whole array each time. The interviewer wants to see if you can save versions without all that copying.

🎯 The Problem

You build an array of a fixed length. Every slot starts at 0. A snapshot is a frozen photo of the array. After you snap, you can keep changing the array, but the old photo never changes.

  • set(index, val) puts a value at a slot.
  • snap() saves the current state and returns a snapshot id. First snap returns 0, next returns 1, and so on.
  • get(index, snapId) returns the value at that slot at the time the given snapshot was taken.
  • The hard part: do this without copying the whole array each time.
SnapshotArray of length 3   -> [0, 0, 0]
set(0, 5)                    -> slot 0 is now 5
snap()                       -> returns 0   (snapshot 0 saved)
set(0, 6)                    -> slot 0 is now 6
get(0, 0)                    -> 5   (slot 0 was 5 at snapshot 0)
snap()                       -> returns 1   (snapshot 1 saved)
set(1, 9)                    -> slot 1 is now 9
get(0, 1)                    -> 6   (slot 0 was 6 at snapshot 1)
get(1, 0)                    -> 0   (slot 1 was never set before snapshot 0)

So get(0, 0) looks back at snapshot 0 and sees 5, even though slot 0 is now 6.

Here is the timeline of changes and snapshots for slot 0.

set(0,5)

snap() -> id 0

set(0,6)

snap() -> id 1

get(0,0)=5, get(0,1)=6

🐢 Approach 1: Copy the Whole Array on Every Snap (Brute Force)

The idea in one line: keep the full array and save a complete copy on every snap.

The idea:

  • On each snap, copy the entire array and store the copy.
  • get just reads from the stored copy.

How it works:

  • Set writes to the live array.
  • Snap saves a full copy and returns the id.
  • Get reads slot index from the copy with that id.

Why it is weak:

  • It saves slots that never changed.
  • Imagine 50000 slots. You change one, then snap. The copy still saves all 50000.
  • Do that many times and memory grows fast.
  • Each snap is O(n), because copying every slot takes time tied to the length.

Here is the full-copy code:

snapshot_array_full_copy.py
class SnapshotArray:
    def __init__(self, length):
        self.current = [0] * length
        self.snaps = []


    def set(self, index, val):
        self.current[index] = val


    def snap(self):
        self.snaps.append(self.current[:])
        return len(self.snaps) - 1


    def get(self, index, snap_id):
        return self.snaps[snap_id][index]

⚡ Approach 2: Per-Index History With Binary Search (Best)

The idea in one line: give each slot its own history of changes, then binary search it to read any past snapshot.

The idea:

  • For each index, keep a list of pairs.
  • Each pair is a snapshot id and the value set at that point. This is the per-index history.
  • A slot stores a pair only when it actually changes.

How set works:

  • Append a pair of the current snap count and the value.
  • If the last pair already has the same snap id, overwrite its value instead.

How snap works:

  • Just increase the snap count and return the old one.
  • Nothing gets copied, so snap is O(1).

How get works:

  • The list is sorted by snapshot id, because ids only go up.
  • Binary search for the latest pair whose id is less than or equal to the asked id.
  • Binary search halves the range each step, so it runs in O(log k) for k changes.
  • If no pair qualifies, return 0, the slot’s starting value.

Why it is fast:

  • An untouched slot stays empty and reads as 0.
  • You store only the changes you actually made, not full copies.

Here is the per-index history and the binary search for get(0, 0).

history of index 0

pair (snap 0, value 5)

pair (snap 1, value 6)

get(0, 0): find largest snap <= 0

return 5

Steps to Solve

  1. Keep a list of histories, one per index. Keep a snap counter starting at 0.
  2. For set, look at the index’s history. If its last pair has the current snap id, overwrite that pair’s value.
  3. Otherwise append a new pair of the current snap id and the value.
  4. For snap, return the current snap counter, then add one to it.
  5. For get, take the index’s history and binary search for the last pair with snap id less than or equal to the asked id.
  6. If a pair is found, return its value. If the history is empty or no pair qualifies, return 0.

This Python version keeps a list of snapshot-value pairs per index and uses the bisect module for binary search.

snapshot_array.py
import bisect




class SnapshotArray:
    def __init__(self, length):
        self.history = [[] for _ in range(length)]  # per index: (snapId, value)
        self.snap_count = 0


    def set(self, index, val):
        h = self.history[index]
        if h and h[-1][0] == self.snap_count:
            h[-1] = (self.snap_count, val)   # overwrite same-snap pair
        else:
            h.append((self.snap_count, val)) # append new pair


    def snap(self):
        self.snap_count += 1
        return self.snap_count - 1           # return old id


    def get(self, index, snap_id):
        h = self.history[index]
        # find insert spot for (snap_id, infinity), then step back one
        pos = bisect.bisect_right(h, (snap_id, float("inf")))
        return h[pos - 1][1] if pos > 0 else 0  # 0 if never set




arr = SnapshotArray(3)
arr.set(0, 5)
print("snap() ->", arr.snap())
arr.set(0, 6)
print("get(0,0) ->", arr.get(0, 0))
print("snap() ->", arr.snap())
arr.set(1, 9)
print("get(0,1) ->", arr.get(0, 1))
print("get(1,0) ->", arr.get(1, 0))

The output of the above code will be:

snap() -> 0
get(0,0) -> 5
snap() -> 1
get(0,1) -> 6
get(1,0) -> 0

Let us walk through the Python get method line by line, because the binary search is the clever part.

    def get(self, index, snap_id):
        h = self.history[index]
        pos = bisect.bisect_right(h, (snap_id, float("inf")))
        return h[pos - 1][1] if pos > 0 else 0

The line h = self.history[index] grabs that one slot’s history. It is a list of pairs, sorted by snapshot id, because ids only go up as time passes.

The line pos = bisect.bisect_right(h, (snap_id, float("inf"))) is the binary search. We search for the pair (snap_id, infinity). The bisect_right call returns the spot just past every pair whose snapshot id is snap_id or smaller. We pair snap_id with infinity so that a pair with the exact same snapshot id still counts as smaller. So pos lands right after the last pair we want.

Why pos - 1? Because pos is one past the pair we need. So the pair just before pos is the latest one with a snapshot id at or below the asked id. The line h[pos - 1][1] reads its value, the second item in the pair.

The line if pos > 0 else 0 handles the empty case. If pos is 0, no pair qualifies. That means the slot was never set at or before this snapshot. The starting value of every slot is 0, so we return 0. That is exactly why get(1, 0) returns 0 in the example.

⏱️ Time and Space Complexity

The naive full copy makes snap O(n) and burns memory on slots that never changed. The per-index history makes set and snap fast, and get a quick binary search. Set appends or overwrites one pair, so it is O(1) on average. Snap just changes a counter, so it is O(1). Get binary searches one slot’s history of k changes, so it is O(log k). Space is only the number of changes you actually made, not the length times the number of snaps.

Approach set snap get Space
Copy whole array per snap O(1) O(n) O(1) O(n times snaps)
Per-index history with binary search O(1) O(1) O(log k) O(total changes)

Tip

The phrase “ask about a past version” is the signal for this pattern. Store only the changes with their version ids, keep them sorted, and binary search for the version you want. It beats copying every time.

🧩 Key Takeaways

  • ✅ Do not copy the whole array on snap. Store only the changes, one history per index.
  • ✅ Each history holds pairs of snapshot id and value, sorted because ids only go up.
  • ✅ snap is O(1), because it just bumps a counter and returns the old value.
  • ✅ get binary searches one slot’s history for the latest pair at or before the asked snapshot.
  • ✅ An untouched slot stores nothing and reads as 0, its starting value.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why is copying the whole array on every snap wasteful?

    Why: A full copy stores all slots each snap, even untouched ones, so memory grows fast.

  2. 2

    What does each index store in the optimal design?

    Why: Each index keeps its own history of (snapId, value) pairs, sorted by snapshot id.

  3. 3

    How does get find the right value for a past snapshot?

    Why: Because the history is sorted by snap id, binary search finds the right pair in O(log k).

  4. 4

    What does get return for a slot that was never set before the asked snapshot?

    Why: Every slot starts at 0, so a slot with no qualifying pair reads as 0.

Score: 0 / 4

🚀 What’s Next?

Previous Design Hit Counter Next All O'one Data Structure