Snapshot Array solution and explanation
Google
9 more videos on this problem
Snapshot Array || Binary Search || Design Problem || Leetcode 1146Aryan Mittal · 19:06 · 7K views
LeetCode 1146. Snapshot Array Explanation and Solutionhappygirlzt · 13:11 · 6K views
Snapshot Array - Leetcode 1146 - PythonTechError · 8:36 · 3K views
Daily Leetcode #1167: Jun 11, 2023 - 1146. Snapshot ArrayProgramming Live with Larry · 14:50 · 888 views
Leetcode 1146 Snapshot Array - Important Data Structure Related Coding Interview QuestionAlgorithmicIQ · 30:08 · 878 views
1146 Snapshot Array |Google | Daily leetcode Challenge | Leetcode POTD | MediumLet's Code Together · 19:27 · 811 views
1146. Snapshot Array (LeetCode)hakunamatasq · 5:44 · 785 views
Leetcode 1146 Snapshot Array (Java)TheAnalyticGuy · 9:44 · 656 views
LeetCode 1146. Snapshot Array (Python)Myron yoo · 4:43 · 598 views
Snapshot Array - LeetCode 1146 - PythonAlpha-Code · 20:47 · 542 views
The problem
Implement a SnapshotArray that supports the following interface:
SnapshotArray(int length)initializes an array-like data structure with the given length. Initially, each element equals 0.void set(index, val)sets the element at the givenindexto be equal toval.int snap()takes a snapshot of the array and returns thesnap_id: the total number of times we calledsnap()minus1.int get(index, snap_id)returns the value at the givenindex, at the time we took the snapshot with the givensnap_id
Example 1:
Input: ["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]] Output: [null,null,0,null,5] Explanation: SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3 snapshotArr.set(0,5); // Set array[0] = 5 snapshotArr.snap(); // Take a snapshot, return snap_id = 0 snapshotArr.set(0,6); snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5
Constraints:
1 <= length <= 5 * 1040 <= index < length0 <= val <= 1090 <= snap_id <(the total number of times we callsnap())- At most
5 * 104calls will be made toset,snap, andget.
Approach overview
Problem Overview: Design a data structure that behaves like an array but supports versioning. You must implement set(index, val), snap(), and get(index, snap_id). Each snapshot freezes the current state of the array, and later queries must return the value at a specific index when that snapshot was taken.
Approach 1: HashMap of Index Changes (set: O(1), snap: O(1), get: O(log k))
Instead of copying the entire array for every snapshot, store only the changes. For each index, maintain a list of pairs (snap_id, value). When you call set(), append the current snapshot id and value for that index. The snap() operation simply increments a global snapshot counter and returns the previous id. When get(index, snap_id) is called, perform binary search on the stored history for that index to find the most recent value whose snapshot id is ≤ the requested one. This design avoids full array duplication and keeps storage proportional to the number of updates. Time complexity is O(1) for updates, O(1) for snapshots, and O(log k) for queries where k is the number of updates to that index. Space complexity is O(m) where m is the total number of set operations. The approach combines ideas from hash tables and binary search to efficiently retrieve historical values.
Approach 2: Versioned Sparse Value Allocation (set: O(1), snap: O(1), get: O(log k))
This design treats each index as a sparse timeline of values. Instead of a generic map structure, maintain an array where each position holds a list of versioned values. Each entry records the snapshot id when a value became active. On set(), append a new version entry only if the value changes during the current snapshot window. The snap() call advances the version counter without copying any data. During get(), perform binary search over the stored versions for that index to locate the value associated with the nearest snapshot ≤ the requested id. Because most indices change infrequently, the structure stays compact. Space usage grows only with actual modifications rather than array size multiplied by snapshots. This approach is common in persistent data structures and versioned storage systems. It relies on efficient indexing using an array combined with binary search over version history.
Recommended for interviews: The HashMap-of-changes approach is the one most interviewers expect. It shows that you recognize the inefficiency of copying the entire array on every snapshot and instead store only the deltas. Mentioning binary search for efficient historical lookup demonstrates strong understanding of time–space tradeoffs. A brute-force full-copy design works conceptually but uses O(n × snaps) space, while the optimized approach scales with the number of updates instead.
Approach 1: Approach 1: HashMap of Index Changes
This approach involves using a dictionary to map each index to another dictionary, which maps the snapshot version to the value at that index. Each call to set(index, val) updates our dictionary for the current snapshot version. When snap() is called, it simply increments the snapshot counter and returns the previous version of the snapshot. For get(index, snap_id), we check the dictionary at that index for the most recent version less than or equal to snap_id.
class SnapshotArray:
def __init__(self, length: int):
self.length = length
self.snap_id = 0
self.snapshots = [{} for _ in range(length)]
def set(self, index: int, val: int) -> None:
self.snapshots[index][self.snap_id] = val
def snap(self) -> int:
self.snap_id += 1
return self.snap_id - 1
def get(self, index: int, snap_id: int) -> int:
while snap_id >= 0 and snap_id not in self.snapshots[index]:
snap_id -= 1
return self.snapshots[index].get(snap_id, 0)import java.util.*;
class SnapshotArray {
private int snapId = 0;
private List<TreeMap<Integer, Integer>> arr;
public SnapshotArray(int length) {
arr = new ArrayList<>(length);
for (int i = 0; i < length; i++) {
arr.add(new TreeMap<>());
}
}
public void set(int index, int val) {
arr.get(index).put(snapId, val);
}
public int snap() {
return snapId++;
}
public int get(int index, int snap_id) {
TreeMap<Integer, Integer> snapMap = arr.get(index);
Map.Entry<Integer, Integer> entry = snapMap.floorEntry(snap_id);
return entry != null ? entry.getValue() : 0;
}
}#include<algorithm>
#include<map>
#include<vector>
class SnapshotArray {
int snap_id = 0;
std::vector<std::map<int, int>> snapshots;
public:
SnapshotArray(int length): snapshots(length) {}
void set(int index, int val) {
snapshots[index][snap_id] = val;
}
int snap() {
return snap_id++;
}
int get(int index, int snap_id) {
const auto& snap_map = snapshots[index];
auto it = snap_map.upper_bound(snap_id);
if (it == snap_map.begin()) return 0;
--it;
return it->second;
}
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int snap_id;
int value;
struct Node *next;
} Node;
typedef struct {
Node **arr;
int length;
int snap_id;
} SnapshotArray;
SnapshotArray* snapshotArrayCreate(int length) {
SnapshotArray* obj = (SnapshotArray*)malloc(sizeof(SnapshotArray));
obj->arr = (Node**)malloc(sizeof(Node*) * length);
obj->length = length;
obj->snap_id = 0;
for (int i = 0; i < length; i++) {
obj->arr[i] = (Node*)malloc(sizeof(Node));
obj->arr[i]->snap_id = -1;
obj->arr[i]->value = 0;
obj->arr[i]->next = NULL;
}
return obj;
}
void snapshotArraySet(SnapshotArray* obj, int index, int val) {
Node* node = (Node*)malloc(sizeof(Node));
node->snap_id = obj->snap_id;
node->value = val;
node->next = obj->arr[index];
obj->arr[index] = node;
}
int snapshotArraySnap(SnapshotArray* obj) {
return obj->snap_id++;
}
int snapshotArrayGet(SnapshotArray* obj, int index, int snap_id) {
Node* curr = obj->arr[index];
while (curr && curr->snap_id > snap_id) {
curr = curr->next;
}
return (curr) ? curr->value : 0;
}
void snapshotArrayFree(SnapshotArray* obj) {
for (int i = 0; i < obj->length; i++) {
Node* curr = obj->arr[i];
while (curr) {
Node* temp = curr;
curr = curr->next;
free(temp);
}
}
free(obj->arr);
free(obj);
}The SnapshotArray is initialized with the given length, creating a list of empty dictionaries, one for each index. The current snap_id starts at 0. The set() method updates the dictionary at the given index for the current snap_id. The snap() method returns the current snap_id and then increments it. The get() method searches backwards for the closest snapshot less than or equal to snap_id that has a value set and returns it.
Time Complexity: O(1) for set() and snap(); O(n) worst-case for get(), where n is the number of snapshots.
Space Complexity: O(l + m) where l is the length of the array, and m is the number of set operations.
Approach 2: Approach 2: Versioned Sparse Value Allocation
This approach takes advantage of a more compact representation by only storing changes using a sorted list of tuples for each index. Each tuple contains a snapshot_id and the corresponding value. This method optimizes memory usage by skipping the storage of unaltered initial values, effectively treating them as zeroes until explicitly set.
class SnapshotArray {
constructor(length) {
this.snapId = 0;
this.arr = Array.from({ length }, () => []);
}
set(index, val) {
let list = this.arr[index];
if (list.length && list[list.length - 1][0] === this.snapId) {
list[list.length - 1][1] = val;
} else {
list.push([this.snapId, val]);
}
}
snap() {
return this.snapId++;
}
get(index, snap_id) {
let list = this.arr[index];
let left = 0, right = list.length;
while (left < right) {
let mid = (left + right) >> 1;
if (list[mid][0] <= snap_id) left = mid + 1;
else right = mid;
}
return right === 0 ? 0 : list[right - 1][1];
}
}using System;
using System.Collections.Generic;
public class SnapshotArray {
private int snapId;
private List<(int, int)>[] snapshots;
public SnapshotArray(int length) {
snapId = 0;
snapshots = new List<(int, int)>[length];
for (int i = 0; i < length; i++) {
snapshots[i] = new List<(int, int)>();
}
}
public void Set(int index, int val) {
var list = snapshots[index];
if (list.Count > 0 && list[list.Count - 1].Item1 == snapId) {
list[list.Count - 1] = (snapId, val);
} else {
list.Add((snapId, val));
}
}
public int Snap() {
return snapId++;
}
public int Get(int index, int snap_id) {
var list = snapshots[index];
int left = 0, right = list.Count;
while (left < right) {
int mid = (left + right) / 2;
if (list[mid].Item1 <= snap_id) left = mid + 1;
else right = mid;
}
return right == 0 ? 0 : list[right - 1].Item2;
}
}In JavaScript, we utilize an array of lists where each list is sorted by snapshot ids. The set() method either updates the last element of the list if the snapshot ids match or appends a new pair. snap() increments the snapshot id. For get(), binary search finds the largest snapshot id less than or equal to snap_id.
Time Complexity: O(log n) for get() due to binary search; O(1) for set() and snap().
Space Complexity: O(l + m).
Approach 3: Array + Binary Search
We maintain an array of length length. Each element in the array is a list, which is used to store the value set each time and the corresponding snapshot ID.
When the set method is called, we add the value and snapshot ID to the list at the corresponding index. The time complexity is O(1).
When the snap method is called, we first increment the snapshot ID, then return the snapshot ID minus one. The time complexity is O(1).
When the get method is called, we use binary search to find the first snapshot ID greater than snap_id at the corresponding position, and then return the previous value. If it cannot be found, return 0. The time complexity is O(log n).
The space complexity is O(n).
class SnapshotArray {
private arr: [number, number][][];
private i: number = 0;
constructor(length: number) {
this.arr = Array.from({ length }, () => []);
}
set(index: number, val: number): void {
this.arr[index].push([this.i, val]);
}
snap(): number {
return this.i++;
}
get(index: number, snap_id: number): number {
let [l, r] = [0, this.arr[index].length];
while (l < r) {
const mid = (l + r) >> 1;
if (this.arr[index][mid][0] > snap_id) {
r = mid;
} else {
l = mid + 1;
}
}
--l;
return l < 0 ? 0 : this.arr[index][l][1];
}
}
/**
* Your SnapshotArray object will be instantiated and called as such:
* var obj = new SnapshotArray(length)
* obj.set(index,val)
* var param_2 = obj.snap()
* var param_3 = obj.get(index,snap_id)
*/type SnapshotArray struct {
arr [][][2]int
i int
}
func Constructor(length int) SnapshotArray {
return SnapshotArray{make([][][2]int, length), 0}
}
func (this *SnapshotArray) Set(index int, val int) {
this.arr[index] = append(this.arr[index], [2]int{this.i, val})
}
func (this *SnapshotArray) Snap() int {
this.i++
return this.i - 1
}
func (this *SnapshotArray) Get(index int, snap_id int) int {
i := sort.Search(len(this.arr[index]), func(i int) bool { return this.arr[index][i][0] > snap_id }) - 1
if i < 0 {
return 0
}
return this.arr[index][i][1]
}
/**
* Your SnapshotArray object will be instantiated and called as such:
* obj := Constructor(length);
* obj.Set(index,val);
* param_2 := obj.Snap();
* param_3 := obj.Get(index,snap_id);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: HashMap of Index Changes | Time Complexity: O(1) for |
| Approach 2: Versioned Sparse Value Allocation | Time Complexity: O(log n) for |
| Array + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Full Snapshot Copy (Brute Force) | set: O(1), snap: O(n), get: O(1) | O(n × snaps) | Conceptual baseline or when array size and snapshot count are very small |
| HashMap of Index Changes | set: O(1), snap: O(1), get: O(log k) | O(m) | General case; optimal for large arrays with many snapshots but relatively few updates |
| Versioned Sparse Value Allocation | set: O(1), snap: O(1), get: O(log k) | O(m) | When implementing persistent or versioned storage patterns |
Frequently asked questions
Is Snapshot Array easy or hard?
Snapshot Array is classified as a Medium difficulty problem. The challenge is recognizing that copying the entire array per snapshot is wasteful and replacing it with a versioned history structure that supports efficient lookups.
Snapshot Array Python/Java solution
In Python and Java, solutions typically maintain an array of lists where each list stores (snap_id, value) pairs. set() appends a new pair, snap() increments a global snapshot counter, and get() uses binary search to locate the most recent entry not exceeding the requested snapshot id.
How to solve Snapshot Array in O(n)?
A naive design copies the entire array during every snap() operation. That approach makes snap() O(n) time and O(n) space per snapshot while keeping get() O(1). Although simple, it becomes inefficient when the number of snapshots grows large, which is why optimized solutions track only updates.
What is the best approach for Snapshot Array?
The most efficient approach stores only value changes instead of full snapshots. Each index keeps a list of (snap_id, value) pairs, and get() performs binary search to find the latest value at or before the requested snapshot. This results in O(1) time for set and snap operations and O(log k) for get, where k is the number of updates to that index.
Is Snapshot Array asked at Google/Amazon/Meta?
Snapshot Array appears in interview preparation lists for companies such as Google, Amazon, and Meta because it tests system design thinking inside a data structure problem. Candidates must optimize memory usage while supporting historical queries efficiently.
What data structure is used in Snapshot Array?
The typical implementation uses arrays combined with hash maps or lists that store versioned values. Each index maintains a sorted history of (snapshot_id, value) entries, and binary search retrieves the correct value for a requested snapshot.
What is the time complexity of Snapshot Array?
Using the optimized design, set() runs in O(1), snap() runs in O(1), and get() runs in O(log k) due to binary search on the version history of that index. Space complexity is O(m), where m is the total number of set operations recorded across all indices.