Problem Description

You need to implement a data structure called SnapshotArray that acts like an array but can save its state at different points in time and retrieve values from those saved states.

The SnapshotArray class should support four operations:

1. Constructor SnapshotArray(int length): Creates an array of the given length where all elements are initially set to 0.

2. Set set(index, val): Updates the element at position index to have value val.

3. Snap snap(): Takes a snapshot of the current array state and returns a snapshot ID. The snapshot ID starts from 0 and increments by 1 with each snapshot taken.

4. Get get(index, snap_id): Retrieves the value at position index as it was when snapshot snap_id was taken.

The key challenge is efficiently storing and retrieving historical values without creating a full copy of the array for each snapshot. The solution uses a space-efficient approach where each array position maintains a list of (snapshot_id, value) pairs, recording only the changes made at each snapshot. When retrieving a value, binary search is used to find the appropriate historical value for the requested snapshot.

For example, if you create a SnapshotArray of length 3, set index 0 to value 5, take a snapshot (getting snap_id 0), then set index 0 to value 6, and take another snapshot (getting snap_id 1), calling get(0, 0) should return 5 (the value at snapshot 0), while get(0, 1) should return 6 (the value at snapshot 1).

Intuition

The naive approach would be to create a complete copy of the entire array every time we take a snapshot. However, this would require O(length) space for each snapshot, which becomes inefficient when we have many snapshots or a large array.

The key observation is that most elements don't change between consecutive snapshots. If an element hasn't been modified since the last snapshot, we don't need to store it again. This leads us to think about storing only the changes (or "deltas") rather than complete copies.

Instead of maintaining multiple copies of the array, we can maintain a history of changes for each index. Each index keeps track of when it was modified and what value it had at that time. This is like keeping a changelog for each array position.

When we need to retrieve a value at a specific snapshot, we look at the history of that index and find the most recent change that occurred before or at the requested snapshot. This is similar to how version control systems work - they don't store complete copies of files but rather the changes made over time.

The challenge then becomes: how do we efficiently find the right historical value? Since changes at each index are naturally ordered by snapshot ID (we always append new changes with increasing snapshot IDs), we can use binary search to quickly locate the appropriate value. We search for the largest snapshot ID that is less than or equal to the requested snap_id.

This approach optimizes space usage because we only store values when they actually change, and it maintains good time complexity for retrieval operations through binary search. Each set operation adds at most one entry, and each get operation performs a binary search on the history of a single index.

Learn more about Binary Search patterns.

Solution Approach

The solution uses an array of lists along with binary search to efficiently manage snapshots.

Data Structure:

• self.arr: An array of length length, where each element is a list storing tuples of (snapshot_id, value) pairs
• self.i: A counter tracking the current snapshot ID

Implementation Details:

1. Initialization (__init__):

   • Create an array of empty lists with self.arr = [[] for _ in range(length)]
   • Initialize snapshot counter self.i = 0
   • Each index starts with an empty history (implicitly representing value 0)

2. Set Operation (set):

   • When setting a value at index, append a tuple (self.i, val) to self.arr[index]
   • This records that at the current snapshot ID, this index has the given value
   • Time complexity: O(1) for appending to a list

3. Snap Operation (snap):

   • Increment the snapshot counter: self.i += 1
   • Return the previous snapshot ID: return self.i - 1
   • Time complexity: O(1)

4. Get Operation (get):

   • Use binary search to find the appropriate historical value
   • bisect_left(self.arr[index], (snap_id, inf)) finds the insertion point for (snap_id, inf)
   • The inf ensures we get the leftmost position if there are multiple entries with the same snapshot ID
   • Subtract 1 from the result to get the last change that occurred at or before snap_id
   • If the result is negative (no changes before this snapshot), return 0 (the initial value)
   • Otherwise, return the value from the found tuple: self.arr[index][i][1]
   • Time complexity: O(log n) where n is the number of changes at this index

Why This Works:

• Changes at each index are naturally sorted by snapshot ID since we only append with increasing snapshot IDs
• Binary search efficiently locates the most recent change before or at the requested snapshot
• Space is optimized as we only store actual changes, not complete array copies
• The use of inf in the binary search ensures we find the correct position even if the exact snap_id doesn't exist in the history

Example Walkthrough

Let's walk through a concrete example to understand how the solution works:

Step 1: Initialize SnapshotArray with length 3

snapshotArr = SnapshotArray(3)

• self.arr = [[], [], []] (three empty lists)
• self.i = 0 (current snapshot ID)

Step 2: Set index 0 to value 5

snapshotArr.set(0, 5)

• Append (0, 5) to self.arr[0]
• self.arr = [[(0, 5)], [], []]
• This records: "At snapshot 0, index 0 has value 5"

Step 3: Take first snapshot

snap_id_0 = snapshotArr.snap()  # returns 0

• Increment self.i from 0 to 1
• Return previous value: 0
• self.arr remains unchanged: [[(0, 5)], [], []]

Step 4: Set index 0 to value 6 and index 1 to value 10

snapshotArr.set(0, 6)
snapshotArr.set(1, 10)

• Append (1, 6) to self.arr[0]
• Append (1, 10) to self.arr[1]
• self.arr = [[(0, 5), (1, 6)], [(1, 10)], []]

Step 5: Take second snapshot

snap_id_1 = snapshotArr.snap()  # returns 1

• Increment self.i from 1 to 2
• Return previous value: 1

Step 6: Get value at index 0 for snapshot 0

value = snapshotArr.get(0, 0)  # returns 5

Binary search process:

• Look at self.arr[0] = [(0, 5), (1, 6)]
• bisect_left([(0, 5), (1, 6)], (0, inf)) returns 1
  • This finds where (0, inf) would be inserted
• Subtract 1: i = 0
• Return self.arr[0][0][1] = 5

Step 7: Get value at index 1 for snapshot 0

value = snapshotArr.get(1, 0)  # returns 0

Binary search process:

• Look at self.arr[1] = [(1, 10)]
• bisect_left([(1, 10)], (0, inf)) returns 0
  • (0, inf) would be inserted at the beginning
• Subtract 1: i = -1
• Since i < 0, no changes existed at snapshot 0, return default value 0

Step 8: Get value at index 1 for snapshot 1

value = snapshotArr.get(1, 1)  # returns 10

Binary search process:

• Look at self.arr[1] = [(1, 10)]
• bisect_left([(1, 10)], (1, inf)) returns 1
  • (1, inf) would be inserted after (1, 10)
• Subtract 1: i = 0
• Return self.arr[1][0][1] = 10

This example demonstrates how:

1. Only changes are stored, not complete array copies
2. Binary search efficiently finds the correct historical value
3. Unmodified indices implicitly maintain their initial value of 0

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(length): O(n) where n is the length parameter, as it creates n empty lists.
• set(index, val): O(1) amortized, as it appends a tuple to the list at the given index.
• snap(): O(1), as it only increments the snapshot counter and returns the previous value.
• get(index, snap_id): O(log m) where m is the number of set operations performed on arr[index], due to the binary search using bisect_left.

Space Complexity:

• The overall space complexity is O(n + s) where n is the initial length and s is the total number of set operations across all indices.
• Initially, O(n) space is allocated for n empty lists.
• Each set operation adds a tuple (snap_id, value) to the corresponding index's list, consuming O(1) additional space per operation.
• In the worst case where all set operations are on different values, the space grows to O(n + s).
• The reference answer stating O(n) appears to consider only the initial allocation or assumes s is bounded by n, but the actual space usage depends on the number of set operations performed.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Overwriting Values Within the Same Snapshot

The Pitfall: A critical issue occurs when set() is called multiple times for the same index within the same snapshot (before calling snap()). The current implementation appends each call as a new entry, creating duplicate snapshot IDs in the history list.

Example of the Problem:

sa = SnapshotArray(3)
sa.set(0, 5)
sa.set(0, 10)  # Same index, same snapshot (0)
sa.snap()      # Returns 0
sa.get(0, 0)   # Returns 5 (incorrect! should return 10)

The history at index 0 becomes: [(0, 5), (0, 10)]. The binary search with bisect_left finds the first occurrence of snapshot 0, returning 5 instead of the last set value of 10.

Solution: Check if the last entry in the history has the same snapshot ID before appending. If it does, update the value instead of appending a new entry:

def set(self, index: int, val: int) -> None:
    history = self.array_history[index]
  
    # If there's already an entry for the current snapshot, update it
    if history and history[-1][0] == self.current_snap_id:
        history[-1] = (self.current_snap_id, val)
    else:
        # Otherwise, append a new entry
        history.append((self.current_snap_id, val))

2. Binary Search Edge Case with bisect_left

The Pitfall: Using bisect_left(history, (snap_id, inf)) - 1 can be confusing and error-prone. The use of inf as a tiebreaker is not immediately intuitive, and developers might incorrectly use bisect_right or forget the -1 adjustment.

Alternative Solution: Use bisect_right with just the snapshot ID for clearer intent:

def get(self, index: int, snap_id: int) -> int:
    history = self.array_history[index]
  
    # Find the rightmost entry with snapshot_id <= snap_id
    # We can use bisect_right with a custom key
    pos = bisect_right(history, snap_id, key=lambda x: x[0]) - 1
  
    if pos < 0:
        return 0
  
    return history[pos][1]

3. Memory Leak from Unnecessary Historical Entries

The Pitfall: If set() is called many times between snapshots, the history list grows unnecessarily large with obsolete intermediate values that will never be queried.

Solution: Only keep the most recent value for each snapshot period by implementing the overwrite logic from pitfall #1. This ensures at most one entry per snapshot ID per index, preventing unbounded growth from repeated sets.