Implement a SnapshotArray that supports:

  • SnapshotArray(int length) – initializes an array of the given length (all zeros)
  • void set(index, val) – sets the element at index to val
  • int snap() – takes a snapshot, returns the snap_id (starting from 0)
  • int get(index, snap_id) – returns the value at index at the time of the given snapshot

Examples

Example 1:

Input:
  SnapshotArray(3), set(0,5), snap(), set(0,6), get(0,0)
Output:
  null, null, 0, null, 5
Explanation:
  set(0,5) → arr = [5,0,0]
  snap()   → snap_id 0 captures [5,0,0]
  set(0,6) → arr = [6,0,0]
  get(0,0) → value at index 0 in snap 0 = 5

Constraints

  • 1 <= length <= 5 * 10^4
  • 0 <= index < length
  • 0 <= val <= 10^9
  • 0 <= snap_id < (number of times snap() was called)
  • At most 5 * 10^4 calls to set, snap, and get

Thinking Process

Naive: Copy Entire Array – O(n) per snap

The simplest approach: maintain a working array and copy it on every snap().

  • set: O(1)
  • snap: O(n) – copies the full array
  • get: O(1)

This works but is too slow and memory-heavy when there are many snapshots and a large array, especially if only a few elements change between snaps.

Bottleneck

Copying the entire array on every snapshot, even when most values haven’t changed.

Optimization: Store Only Changes

Instead of copying the full array, for each index store a sorted log of (snap_id, value) pairs – only recording when a value actually changes.

On get(index, snap_id): binary search for the latest entry at or before snap_id.

A map<int,int> per index gives this naturally with upper_bound.

Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search O(log n) O(1) Sorted array, left <= right
Lower / upper bound O(log n) O(1) First/last position, insert index
Binary search on rotated array (this problem) O(log n) O(1) Identify sorted half, discard other
Binary search on answer O(n log M) O(1) Monotonic predicate over search space

Solution

class SnapshotArray:
    def __init__(self, length: int):
        self.arr = [0] * length
        self.snaps: list[list[int]] = []

    def set(self, index: int, val: int) -> None:
        self.arr[index] = val

    def snap(self) -> int:
        sid = len(self.snaps)
        self.snaps.append(self.arr[:])
        return sid

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

Solution Explanation

Approach: Binary search on rotated array (this problem)

Key idea: ### Naive: Copy Entire Array – O(n) per snap

How the code works:

  • set: O(1)
  • snap: O(n) – copies the full array
  • get: O(1)

Walkthrough — input SnapshotArray(3), set(0,5), snap(), set(0,6), get(0,0), expected output null, null, 0, null, 5:

set(0,5) → arr = [5,0,0] snap() → snap_id 0 captures [5,0,0] set(0,6) → arr = [6,0,0] get(0,0) → value at index 0 in snap 0 = 5

Comparison

Approach set snap get Space
Copy Array O(1) O(n) O(1) O(n · text{snaps})
Map + Binary Search O(log S) O(1) O(log S) O(text{total sets})

The map approach wins when snapshots are frequent but changes are sparse.

Common Mistakes

  • Forgetting to initialize data[i][0] = 0 (without it, get on an index that was never set returns garbage)
  • Using lower_bound instead of upper_bound (off-by-one on the snap boundary)
  • Storing snapshots in the wrong direction (value at snap time, not snap at value time)

Key Takeaways

  • “Versioned data with sparse updates” = store change log per element + binary search
  • upper_bound then decrement is the standard pattern for “latest version at or before X”
  • The optimization from O(n) snap to O(1) snap comes from only recording diffs, not full copies

References

Template Reference