Coding Interview PatternsSnapshot Array
MediumCustom Data Structures

Snapshot Array

Explanation & Solution

Practice Problem

Description

Design a data structure that supports taking snapshots of an array and querying past values.

Implement a function that processes an array of operations and an array of arguments:

  • "SnapshotArray" — Initializes the array of the given length. All elements start at 0.
  • "set" — Sets arr[index] = val.
  • "snap" — Takes a snapshot of the array and returns the snap_id (starts at 0, increments with each call).
  • "get" — Returns the value at arr[index] as of the snapshot with snap_id.
Input:operations = ["SnapshotArray","set","snap","set","get"], args = [[3],[0,5],[],[0,6],[0,0]]
0
SnapshotArray
1
set
2
snap
3
set
4
get
Output:[null,null,0,null,5]
0
null
1
null
2
0
3
null
4
5

Explanation: Initialize array of length 3. Set index 0 to 5. Take snapshot (returns 0). Set index 0 to 6. Get index 0 at snap_id 0 returns 5 (the value before the update).

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

Approach

Custom Data Structures pattern

1. Per-Index Version History

  • For each index, store a list of [snapId, value] pairs
  • Only record an entry when the value actually changes (sparse storage)
  • Initialize each index with [[0, 0]] — snap 0, value 0

2. Implement Set

  • If the last recorded snap ID for this index equals the current snapId, update the value in-place
  • Otherwise, append a new [snapId, value] entry
  • This avoids creating redundant entries for multiple sets within the same snapshot

3. Implement Snap

  • Simply return and increment snapId
  • No need to copy the entire array — changes are tracked per-index lazily

4. Implement Get with Binary Search

  • Each index has a sorted list of [snapId, value] pairs
  • Binary search for the largest snapId ≤ sid to find the value at that snapshot
  • Use upper-bound style binary search: find the rightmost entry whose snapId ≤ sid

5. Why Binary Search?

  • Naively scanning would be O(number of snaps) per query
  • Since the history per index is sorted by snapId, binary search gives O(log n)

Key Insight

  • Only storing changes (not full copies) makes this memory-efficient for sparse updates
  • The binary search retrieves the "most recent version before or at snap_id"
Time
O(log n) for get, O(1) amortized for set/snap
Space
O(total number of set calls)

Solution Code

Previous
Insert Delete GetRandom O(1)
Next
Design Underground System