1146. Snapshot Array
Problem Description
The task is to create a data structure called SnapshotArray
that represents an array-like entity where snapshots of the array's state can be taken at different times. Initially, the array is of a given length and all elements are set to 0
. The SnapshotArray
should support the following operations:
-
Initialization: When an instance of
SnapshotArray
is created, it should be initialized with a certain length. All elements should be set to0
. -
Set: There should be a function that updates the value of an element at a particular index. This means changing the element's value to a new one.
-
Snap: This function takes a snapshot of the current state of the array and returns an identifier for this snapshot, known as
snap_id
. Thesnap_id
starts from0
and increments by1
each time a new snapshot is taken. -
Get: Given an
index
and asnap_id
, this function should return the value of the element at the given index as it was during the snapshot identified bysnap_id
.
Intuition
To solve this problem, we need a way to efficiently record the changes to each element of the array over time—this is done so that we can later query the value of an element as it was at any snapshot point.
Here's the intuition explained step by step:
-
Initialization: We use a
defaultdict
of lists to represent theSnapshotArray
. This allows us to keep a history of changes for each index. Each entry in the list will be a tuple consisting of asnap_id
and a value, representing the value of the array at that index after the snapshot was taken. -
Set: When setting a value at an index, we append a tuple to the list at that index containing the current
snap_id
and the new value. This way, we are effectively recording a timeline of values for each index. -
Snap: This operation increments the
snap_id
used to track the snapshots and returns the previoussnap_id
. -
Get: To retrieve a value from a past snapshot, we use binary search (
bisect_right
) to find the first tuple where thesnap_id
is greater than the requestedsnap_id
. We then take the previous tuple as it will have the value of the array at the time of the snapshot. If there is no such tuple (i.e., if the index was never set before thesnap_id
), we return0
.
The solution uses binary search for efficient retrieval of the historical value and defaultdict
to avoid having to initialize every index which makes it space-efficient if many indices remain at the initial value 0
.
Learn more about Binary Search patterns.
Solution Approach
The implementation of the SnapshotArray
uses a combination of data structures and algorithms to provide an efficient way to execute the required operations.
Here's how each part of the solution approach works:
-
A
defaultdict
is used to initialize thearr
attribute. Thedefaultdict
from Python'scollections
library creates a new list for each new key by default, which is ideal for our case where a key represents an index in the SnapshotArray, and the value is a list that stores the history of values set at that index along with their correspondingsnap_id
. -
The
set
method appends a tuple(```self.idx````,
val)
to the list at the specified index. If the index is being set for the first time, thedefaultdict
will create an empty list and then append to it. It records the current snapshot indexself.idx
alongside the valueval
. -
The
snap
method incrementsself.idx
, the internal snapshot index, and returns the previous snapshot index by doingself.idx - 1
. This operation assigns a new snapshot identifier and ensures that subsequentset
operations will be considered part of a new snapshot. -
The
get
method retrieves the value for a given index at a specific snapshot. It uses binary search to find the correct value.bisect_right(vals, (```snap_id````, inf))
finds the insertion point invals
, which is the list of all values set forindex
, to maintain the sorted order ifsnap_id
were to be added tovals
. Since we want the most recent set operation before or equal tosnap_id
, we take one step back with- 1
. If the resultant indexi
is negative, it means noset
operations were done beforesnap_id
, so it returns0
. Otherwise, it returns the value, which is the second element of the tuplevals[i][1]
.
The essential patterns used in this implementation are:
-
Lazy Update: Instead of updating all values at each snapshot, we only record changes. This saves on unnecessary operations and space since unchanged elements are assumed to keep their previous values.
-
History of Operations: Keeping a list of all operations
(snap_id, value)
allows us to reconstruct the state at any snapshot time. -
Binary Search: To efficiently find the required state from the historical operations, we use binary search, which gives us a
O(log n)
time complexity, wheren
is the number of operations recorded for an index.
In conclusion, the SnapshotArray
is efficiently implemented using defaultdict
for lazy update initialization, appending operations to lists to maintain a complete history, and utilizing binary search for quick retrieval.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach for implementing SnapshotArray
.
- Initialization
Create a
SnapshotArray
instance with a length of 3.
snapArray = SnapshotArray(3) // The internal structure now is: {0: [(0, 0)], 1: [(0, 0)], 2: [(0, 0)]}, // with snap_id initialized at 0.
- Set Operation Set the value at index 1 to 5.
snapArray.set(1, 5) // The internal structure is now: {0: [(0, 0)], 1: [(0, 5)], 2: [(0, 0)]}. // As the current snap_id is 0, we record that index 1 has value 5 after snapshot 0.
- Snap Operation Take a snapshot.
snap_id_0 = snapArray.snap() // This increments the internal snap_id to 1 and returns 0. // The internal structure is still: {0: [(0, 0)], 1: [(0, 5)], 2: [(0, 0)]}.
- Set Operation Set the value at index 1 to 6.
snapArray.set(1, 6) // The internal structure is now: {0: [(0, 0)], 1: [(0, 5), (1, 6)], 2: [(0, 0)]}. // Since the current snap_id is 1, we record that index 1 has value 6 after snapshot 1.
- Get Operation
Get the value at index 1 with
snap_id
0.
value = snapArray.get(1, 0) // Here we perform a binary search to find the first entry in the list at index 1 // that would come after (0, inf) if it were inserted, which is the tuple (1, 6). // We take the previous tuple (0, 5) and return the value 5. // The method would return 5, the value at index 1 during snapshot 0.
- Snap Operation Take another snapshot.
snap_id_1 = snapArray.snap() // This increments the internal snap_id to 2 and returns 1. // The internal structure is unchanged.
- Get Operation
Get the value at index 1 with
snap_id
1.
value = snapArray.get(1, 1) // The method looks for the entry after (1, inf) and finds nothing, so it returns the last value before, // which is from the tuple (1, 6). Therefore, it returns 6, the value at index 1 during snapshot 1.
- Get Operation
Get the value at index 2 with
snap_id
1.
value = snapArray.get(2, 1)
// Since index 2 has not been set after snapshot 0, binary search finds
// the first tuple (0, 0) and returns 0 since there are no changes.
Through this example, we have shown how set
, snap
, and get
operations interact with the SnapshotArray
's underlying data structure. We used defaultdict
to initialize the snapshot array lazily, appended changes at each set
operation, and applied binary search during the get
operation to efficiently retrieve the correct historical value.
Solution Implementation
1from collections import defaultdict
2from bisect import bisect_right
3from math import inf
4
5class SnapshotArray:
6 def __init__(self, length: int):
7 # Initialize an index counter for snapshots and a default dictionary
8 # to store values with their corresponding snapshot indices.
9 self.snapshot_index = 0
10 self.array_data = defaultdict(list)
11
12 def set(self, index: int, val: int) -> None:
13 """
14 Set the value at a particular index to the specified value
15 within the latest snapshot.
16 """
17 # Append the current snapshot index and val to the list at the given index.
18 self.array_data[index].append((self.snapshot_index, val))
19
20 def snap(self) -> int:
21 """
22 Take a snapshot of the array, incrementing the snapshot index.
23 """
24 # Increment the snapshot index and return the ID of the snapshot taken.
25 self.snapshot_index += 1
26 return self.snapshot_index - 1
27
28 def get(self, index: int, snap_id: int) -> int:
29 """
30 Get the value at the specified index at the time of the given snapshot.
31 """
32 # Retrieve the list of value-snapshot index pairs for the given index.
33 value_snapshots = self.array_data[index]
34 # Find the rightmost value such that it's snapshot index is less than or equal to snap_id.
35 i = bisect_right(value_snapshots, (snap_id, inf)) - 1
36 # Return 0 if no such index is found, otherwise return the value at that index.
37 return 0 if i < 0 else value_snapshots[i][1]
38
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class SnapshotArray {
6 private final List<int[]>[] snapshotArray; // An array of lists to hold the elements at different snapshots
7 private int currentSnapId; // To keep track of the current snapshot id
8
9 // Constructor
10 public SnapshotArray(int length) {
11 // Initialize the array of lists with the given length
12 snapshotArray = new List[length];
13 // Fill each list within the array
14 Arrays.setAll(snapshotArray, k -> new ArrayList<>());
15 }
16
17 // Set a value at a particular index
18 public void set(int index, int val) {
19 /* Add a pair (snapshot id, value) to the corresponding index.
20 * If a snapshot is taken after this, it will have the new value. */
21 snapshotArray[index].add(new int[] {currentSnapId, val});
22 }
23
24 // Take a snapshot of the array and return the current snapshot id
25 public int snap() {
26 // Increase the snapshot id and return the id of the snapshot taken
27 return currentSnapId++;
28 }
29
30 // Get the value at a specific index for a given snapshot
31 public int get(int index, int snapId) {
32 // List for values at the index
33 List<int[]> values = snapshotArray[index];
34 // Binary search to find the floor entry of the provided snapId
35 int left = 0, right = values.size();
36 while (left < right) {
37 int mid = (left + right) / 2; // mid-point for binary search
38 // If the mid snapshot id is greater than snapId, search on the left
39 if (values.get(mid)[0] > snapId) {
40 right = mid;
41 } else {
42 // If not, search on the right
43 left = mid + 1;
44 }
45 }
46 // If there's no element, return 0. Otherwise, return the value found at the snapId
47 return left == 0 ? 0 : values.get(left - 1)[1];
48 }
49}
50
51/**
52 * Usage:
53 * SnapshotArray obj = new SnapshotArray(length);
54 * obj.set(index, val);
55 * int snapId = obj.snap();
56 * int value = obj.get(index, snapId);
57 */
58
1#include <vector>
2using std::vector;
3using std::pair;
4
5class SnapshotArray {
6public:
7 // Initialize the SnapshotArray with a specific length.
8 SnapshotArray(int length) : idx(0), snaps(length) {
9 }
10
11 // Sets the element at the given index to the given value.
12 void set(int index, int val) {
13 // Append a new pair of the current "snapshot index" and value to the changes of the specified index.
14 snaps[index].push_back({idx, val});
15 }
16
17 // Takes a snapshot of the array and returns the index of the snapshot.
18 int snap() {
19 // Increase and return the current snapshot index.
20 return idx++;
21 }
22
23 // Retrieves the value at the given index according to the specified snapshot id.
24 int get(int index, int snap_id) {
25 auto& changes = snaps[index]; // A reference to the list of value changes for the specified index.
26 int left = 0, right = changes.size(); // Binary search bounds.
27
28 // Perform a binary search to find the first change with snapshot index greater than snap_id.
29 while (left < right) {
30 int mid = (left + right) >> 1; // Calculate the middle point using bitwise shift.
31 if (changes[mid].first > snap_id) {
32 right = mid;
33 } else {
34 left = mid + 1;
35 }
36 }
37
38 // If left is 0, it means no changes were recorded for the index until snap_id, so return 0.
39 // Otherwise, return the value before the first change that has snapshot index greater than snap_id.
40 return left == 0 ? 0 : changes[left - 1].second;
41 }
42
43private:
44 vector<vector<pair<int, int>>> snaps; // A 2D vector to store the value changes for each index.
45 int idx; // The current snapshot index.
46};
47
48/*
49 * Your SnapshotArray object will be instantiated and called as such:
50 * SnapshotArray* obj = new SnapshotArray(length);
51 * obj->set(index, val);
52 * int snapIndex = obj->snap();
53 * int val = obj->get(index, snap_id);
54 */
55
1// Define the snapshot index and the array to hold snapshot data.
2let snapshotIndex: number = 0;
3let snapshotArray: Array<Array<[number, number]>> = [];
4
5// Function to initialize the SnapshotArray with a specific length.
6function initializeSnapshotArray(length: number): void {
7 snapshotIndex = 0;
8 snapshotArray = new Array(length).fill(null).map(() => []);
9}
10
11// Function to set the element at the given index to the given value.
12function setSnapshotArrayValue(index: number, value: number): void {
13 const changes = snapshotArray[index];
14 changes.push([snapshotIndex, value]);
15}
16
17// Function to take a snapshot of the array and return the index of the snapshot.
18function snapSnapshotArray(): number {
19 return snapshotIndex++;
20}
21
22// Function to retrieve the value at the given index according to the specified snapshot ID.
23function getSnapshotArrayValue(index: number, snapshotId: number): number {
24 const changes = snapshotArray[index];
25 let left = 0;
26 let right = changes.length;
27
28 // Perform a binary search to find the element with snapshotId less than or equal to the requested snapshotId.
29 while (left < right) {
30 const mid: number = (left + right) >> 1;
31 if (changes[mid][0] > snapshotId) {
32 right = mid;
33 } else {
34 left = mid + 1;
35 }
36 }
37
38 // If left is 0, it means no changes were recorded for the index until snapshotId, return 0.
39 // Otherwise, return the last value before the snapshotId increased.
40 return left === 0 ? 0 : changes[left - 1][1];
41}
42
43// Example usage:
44// initializeSnapshotArray(3); // Initialize it with a length of 3.
45// setSnapshotArrayValue(0, 5); // Set the first element to 5.
46// const snapId = snapSnapshotArray(); // Take a snapshot and get the snapshot ID.
47// const value = getSnapshotArrayValue(0, snapId); // Get the value at index 0 for this snapshot ID.
48
Time and Space Complexity
Time Complexity
__init__
: O(1) - Initializing the array and idx takes constant time.set
: O(1) - Appending a value to the array list at a given index is an amortized constant time operation.snap
: O(1) - Incrementing the snapshot index is a constant time operation.get
: O(log S) - Using binary search (bisect_right
) where S is the number of snapshots at a particular index. This is because binary search has logarithmic time complexity relative to the number of elements it is searching through.
Space Complexity
- Overall: O(N * S) - Every set operation could be in a new index and could create up to S snapshots for every index in the worst case, where N is the number of indices in the
SnapshotArray
and S is the number of snapshots taken per index.
Each entry in arr
is a tuple storing two integers (snap_id, value), so every set
operation adds another tuple to the space used by the data structure.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!