1146. Snapshot Array

MediumDesignArrayHash TableBinary Search
Leetcode Link

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:

  1. Initialization: When an instance of SnapshotArray is created, it should be initialized with a certain length. All elements should be set to 0.

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

  3. Snap: This function takes a snapshot of the current state of the array and returns an identifier for this snapshot, known as snap_id. The snap_id starts from 0 and increments by 1 each time a new snapshot is taken.

  4. Get: Given an index and a snap_id, this function should return the value of the element at the given index as it was during the snapshot identified by snap_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:

  1. Initialization: We use a defaultdict of lists to represent the SnapshotArray. This allows us to keep a history of changes for each index. Each entry in the list will be a tuple consisting of a snap_id and a value, representing the value of the array at that index after the snapshot was taken.

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

  3. Snap: This operation increments the snap_id used to track the snapshots and returns the previous snap_id.

  4. Get: To retrieve a value from a past snapshot, we use binary search (bisect_right) to find the first tuple where the snap_id is greater than the requested snap_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 the snap_id), we return 0.

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 the arr attribute. The defaultdict from Python's collections 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 corresponding snap_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, the defaultdict will create an empty list and then append to it. It records the current snapshot index self.idx alongside the value val.

  • The snap method increments self.idx, the internal snapshot index, and returns the previous snapshot index by doing self.idx - 1. This operation assigns a new snapshot identifier and ensures that subsequent set 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 in vals, which is the list of all values set for index, to maintain the sorted order if snap_id were to be added to vals. Since we want the most recent set operation before or equal to snap_id, we take one step back with - 1. If the resultant index i is negative, it means no set operations were done before snap_id, so it returns 0. Otherwise, it returns the value, which is the second element of the tuple vals[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, where n 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's go through a small example to illustrate the solution approach for implementing SnapshotArray.

  1. Initialization Create a SnapshotArray instance with a length of 3.
1snapArray = SnapshotArray(3)
2// The internal structure now is: {0: [(0, 0)], 1: [(0, 0)], 2: [(0, 0)]},
3// with snap_id initialized at 0.
  1. Set Operation Set the value at index 1 to 5.
1snapArray.set(1, 5)
2// The internal structure is now: {0: [(0, 0)], 1: [(0, 5)], 2: [(0, 0)]}.
3// As the current snap_id is 0, we record that index 1 has value 5 after snapshot 0.
  1. Snap Operation Take a snapshot.
1snap_id_0 = snapArray.snap()
2// This increments the internal snap_id to 1 and returns 0.
3// The internal structure is still: {0: [(0, 0)], 1: [(0, 5)], 2: [(0, 0)]}.
  1. Set Operation Set the value at index 1 to 6.
1snapArray.set(1, 6)
2// The internal structure is now: {0: [(0, 0)], 1: [(0, 5), (1, 6)], 2: [(0, 0)]}.
3// Since the current snap_id is 1, we record that index 1 has value 6 after snapshot 1.
  1. Get Operation Get the value at index 1 with snap_id 0.
1value = snapArray.get(1, 0)
2// Here we perform a binary search to find the first entry in the list at index 1
3// that would come after (0, inf) if it were inserted, which is the tuple (1, 6).
4// We take the previous tuple (0, 5) and return the value 5.
5// The method would return 5, the value at index 1 during snapshot 0.
  1. Snap Operation Take another snapshot.
1snap_id_1 = snapArray.snap()
2// This increments the internal snap_id to 2 and returns 1.
3// The internal structure is unchanged.
  1. Get Operation Get the value at index 1 with snap_id 1.
1value = snapArray.get(1, 1)
2// The method looks for the entry after (1, inf) and finds nothing, so it returns the last value before,
3// which is from the tuple (1, 6). Therefore, it returns 6, the value at index 1 during snapshot 1.
  1. Get Operation Get the value at index 2 with snap_id 1.
1value = snapArray.get(2, 1)
2// Since index 2 has not been set after snapshot 0, binary search finds 
3// 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.


Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄