1146. Snapshot Array
Asked at Apple, Databricks, Netflix
Difficulty
Medium
Time
set: O(1), snap: O(1), get: O(lo
Space
O(total number of set calls)
Pattern
Array
Companies
3
Problem
Design a data structure that behaves like an array of a fixed length, where every element starts at 0. It must support three operations.
set(index, val) changes the element at index to val. snap() freezes the current state of the whole array and returns a snap_id — the first call returns 0, the next returns 1, and so on. get(index, snap_id) asks: what was the value at index at the moment that snapshot was taken?
The tricky part is that snap() must be cheap. You cannot copy the whole array on every snapshot, because the array can be large and there can be many snapshots. Also note that a get for a snapshot taken before any set on that index must return 0.
Snapshots freeze the past
Constraints
- ●
1 <= length <= 5 * 10^4 - ●
0 <= index < length - ●
0 <= val <= 10^9 - ●
0 <= snap_id < total number of snap() calls - ●
At most 5 * 10^4 total calls to set, snap and get
Examples
["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]][null,null,0,null,5]["SnapshotArray","snap","get","set","snap","get","get"]
[[1],[],[0,0],[0,10],[],[0,1],[0,0]][null,0,0,null,1,10,0]Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Databricks | Medium | View all Databricks questions → |
| Netflix | Medium | View all Netflix questions → |
How to Think About It
Store history per index: each index has a list of (snap_id, value) pairs. On set(index, val), append (current_snap, val) to that index's history.
On snap(), increment the global snap_id counter. No data is copied, making snap O(1).
On get(index, snap_id), binary search that index's history for the largest snap_id <= the requested snap_id. This finds the most recent value at or before that snapshot.
Edge cases: get before any set (return 0), multiple sets at same index without snap (each gets same snap_id), get with snap_id = 0 after initial snap.
Optimal Approach
Data structure: array of lists, where each list stores (snap_id, value) pairs.
set(index, val):
Append (current_snap_id, val) to history[index].
snap():
Increment current_snap_id. Return the old value.
get(index, snap_id):
Binary search history[index] for the largest pair with snap_id <= given snap_id.
If found, return its value. Otherwise return 0.
Time: set is O(1). snap is O(1). get is O(log k) where k is the number of sets at that index. Space: O(total_sets).
History per index, binary search on get
What Trips People Up in Real Interviews
Copying the entire array on every snap(). This makes snap() O(n) and defeats the purpose. The correct approach is O(1) snap by just incrementing a counter. Each index stores only the changes, not the full array.
Using a single flat list of all snapshots instead of per-index history. A flat list forces O(n) lookup per get() because you must search through every index at each snap. Per-index history limits binary search to only the changes at that index.
Binary searching for exact snap_id match instead of largest snap_id <= target. Values are only recorded when set() is called. Between snaps, the value stays the same. You need the most recent version at or before the requested snap, not an exact match.
Forgetting that multiple set() calls between two snap() calls share the same snap_id. This means history[index] can have consecutive entries with identical snap_id. The binary search must handle this correctly by taking the last entry with snap_id <= target.
Not initializing the result to 0. If no set() has been called at an index before the requested snap, the value is 0 by default. Forgetting this default and returning None or throwing an error fails edge cases.
Solution Code
set: O(1), snap: O(1), get: O(lo timeimport bisect
class SnapshotArray:
def __init__(self, length):
self.snap_id = 0
self.history = [[] for _ in range(length)]
def set(self, index, val):
self.history[index].append((self.snap_id, val))
def snap(self):
self.snap_id += 1
return self.snap_id - 1
def get(self, index, snap_id):
history = self.history[index]
lo, hi = 0, len(history) - 1
result = 0
while lo <= hi:
mid = (lo + hi) // 2
if history[mid][0] <= snap_id:
result = history[mid][1]
lo = mid + 1
else:
hi = mid - 1
return resultFrequently Asked Questions
What is the Snapshot Array problem?
Implement a Snapshot Array that supports the following: set(index, val) sets the value at a given index, snap() takes a snapshot and returns the snapshot ID, and get(index, snap_id) returns the value at the given index in the most recent snapshot taken before or at snap_id.
How do you solve Snapshot Array?
The optimal approach runs in set: O(1), snap: O(1), get: O(lo time and O(total number of set calls) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Snapshot Array?
Snapshot Array is asked at Apple, Databricks, Netflix. It is a medium difficulty problem.
What are common mistakes on Snapshot Array?
- Copying the entire array on every `snap()`. This makes `snap()` `O(n)` and defeats the purpose. The correct approach is `O(1)` snap by just incrementing a counter. Each index stores only the changes, not the full array.
- Using a single flat list of all snapshots instead of per-index history. A flat list forces `O(n)` lookup per `get()` because you must search through every index at each snap. Per-index history limits `binary search` to only the changes at that index.
- Binary searching for exact `snap_id` match instead of largest `snap_id <= target`. Values are only recorded when `set()` is called. Between snaps, the value stays the same. You need the most recent version at or before the requested snap, not an exact match.
- Forgetting that multiple `set()` calls between two `snap()` calls share the same `snap_id`. This means `history[index]` can have consecutive entries with identical `snap_id`. The `binary search` must handle this correctly by taking the last entry with `snap_id <= target`.
- Not initializing the result to 0. If no `set()` has been called at an index before the requested snap, the value is 0 by default. Forgetting this default and returning `None` or throwing an error fails edge cases.