Skip to main content
Talentd

Snapshot Array - Solution & Explanation

MediumArrayHash TableBinary SearchDesign16 min readAsked at: Amazon, Microsoft, Apple +17
Practice this problem

Problem Statement

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 given index to be equal to val.
  • int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
  • int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_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 * 104
  • 0 <= index < length
  • 0 <= val <= 109
  • 0 <= snap_id < (the total number of times we call snap())
  • At most 5 * 104 calls will be made to set, snap, and get.

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.

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.

Code

PythonC++JavaC

Python

C++

Java

C

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(log n) for get() due to binary search; O(1) for set() and snap().
Space Complexity: O(l + m).

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: HashMap of Index Changes

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: Versioned Sparse Value Allocation

Time Complexity: O(log n) for get() due to binary search; O(1) for set() and snap().
Space Complexity: O(l + m).

Array + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 Changesset: 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 Allocationset: O(1), snap: O(1), get: O(log k)O(m)When implementing persistent or versioned storage patterns

Video Solution

Snapshot Array || Binary Search || Design Problem || Leetcode 1146 • Aryan Mittal • 7,344 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Snapshot Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays