1146. Snapshot Array

1146

MediumData Structure DesignSorted (snap_id, value) log per cell, queried by binary searchPer-index version history with binary search on snapshot id

Snapshot Array

Implement a SnapshotArray of a given length, initialized to all zeros. set(index, val) writes a value. snap() takes a snapshot and returns the id (0-based, one less than the number of snaps taken). get(index, snap_id) returns the value at that index at the time the given snapshot was taken.

Open official problem prompt ↗

In plain English

Answer 'what was this cell's value at snapshot t?' efficiently while spending memory only on cells that actually changed.

Picture it like this

Like a document's version history: instead of photocopying the whole document on every save, you record only the edited lines with a version stamp, then jump to the right version when asked.

Example

Input: SnapshotArray(3); set(0, 5); snap(); set(0, 6); get(0, 0)
Output: [null, null, 0, null, 5]
Why: set(0,5) then snap() returns id 0 while index 0 held 5; the later set(0,6) happens after snapshot 0, so get(0,0) still reports 5.

Constraints

1 <= length <= 5 * 10^40 <= index < length0 <= val <= 10^90 <= snap_id < (number of times snap has been called)At most 5 * 10^4 calls total to set, snap, and get

Pattern lesson

See the pattern, then code

Per-index version history with binary search on snapshot id

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. Only cells that change need new records. For each index keep a list of (snap_id, value) pairs in increasing snap_id order; a get is a binary search for the last record whose snap_id does not exceed the queried snapshot.

New words, made simpleKnow these before the algorithm

Snapshot id: A version number assigned each time snap() is called; get queries against one of these.
Version log: The ordered list of (snap_id, value) records for one index.
bisect_right: Binary search returning the insertion point just past matching keys, used to find the newest record at or before a snapshot.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Copy the whole array on each snap

Up to 5*10^4 snaps of a 5*10^4 array is billions of cells — memory blows up.

Store a full array snapshot for every snap() call.

Time O(length) per snap, O(1) getSpace O(length * snaps)

Best choicePer-index (snap_id, value) log + binary search

Memory scales with actual edits, and lookups stay logarithmic.

Record a change only when a cell is written; binary-search history on get.

Time O(log m) getSpace O(number of writes)

The rule we keep true

Invariant

Each index's history is strictly increasing in snap_id, and each record (s, v) means 'from snapshot s until the next recorded snapshot, this cell held v'.

Why this is correct

Reasoning

Values only change on set, so the newest record with snap_id <= t is exactly the value in effect at snapshot t. Overwriting the last record when its snap_id equals the current snap_id keeps at most one record per index per snapshot, and binary search finds the effective record in log time.

The algorithm in three movesSay these aloud before coding

1Give each index a history starting with (0, 0)

set(0,5): history[0]=[(0,5)] (snap_id 0)

2On set, if the last record already has the current snap_id overwrite it, else append (snap_id, val)

snap(): snap_id -> 1, return 0

3On snap, increment the counter and return the previous value

get(0,0): bisect finds (0,5) -> 5

4On get, binary-search the index's history for the largest snap_id <= the queried id and return its value

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

(0,0)0

(0,5)1

(1,6)2

1 · Readlength 3

2 · AskInitial state?

3 · Update stateeach history = [(0,0)], snap_id=0

4 · Resultall cells default to 0

Key takeaway

Index 0's history log; get(0,0) binary-searches for the last entry with snap_id <= 0, landing on (0,5).

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-6Initialization
Every index seeds a history with (0,0) so unset cells read as 0 at any snapshot.
2
Lines 8-13set
Overwrite in place when the current snapshot already has a record for this index; otherwise append a new versioned record.
3
Lines 15-17snap
Bump the global version counter and return the id just consumed.
4
Lines 19-22get
bisect_right with a +inf sentinel value finds the last record whose snap_id <= the query, then reads its value.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

get on an index never set (returns the seeded 0)
Multiple set calls to the same index within one snapshot (only the last survives)
get at snap_id 0 before any changes
Large val up to 10^9 handled as plain ints

Common beginner mistakes

Copying the entire array per snap and running out of memory
Using bisect_left or forgetting the -1, landing on the wrong record
Not deduplicating writes within the same snapshot, bloating histories and breaking the overwrite assumption
Returning snap_id instead of snap_id-1 from snap()

Check your understanding

Why does bisect_right on (snap_id, +inf) then subtracting one return the correct record?

PyPython 3 · solution.py

Optimal

1import bisect23class SnapshotArray:4    def __init__(self, length: int):5        self.snap_id = 06        self.history = [[(0, 0)] for _ in range(length)]78    def set(self, index: int, val: int) -> None:9        h = self.history[index]10        if h[-1][0] == self.snap_id:11            h[-1] = (self.snap_id, val)12        else:13            h.append((self.snap_id, val))1415    def snap(self) -> int:16        self.snap_id += 117        return self.snap_id - 11819    def get(self, index: int, snap_id: int) -> int:20        h = self.history[index]21        i = bisect.bisect_right(h, (snap_id, float('inf'))) - 122        return h[i][1]

Time complexityO(1) set and snap; O(log m) get where m is the number of writes to that indexOptimized

Space complexityO(total number of set calls + length)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonUber

Snapshot Array

Snapshot Array

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design