#1146

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Snapshot Array

Implement a SnapshotArray that efficiently tracks element changes and retrieves past states using array scanning and hash lookup patterns.

array hash table binary search design

Problem Statement

Design a SnapshotArray class that supports initializing with a given length and provides set, snap, and get methods. The set method updates an element at a specified index, snap captures a snapshot of the current state and returns a unique snap_id, and get retrieves the value at a given index for a specific snap_id.

Constraints include array length up to 5 * 10^4, element values up to 10^9, snap_id within the number of snapshots taken, and up to 5 * 10^4 calls across all methods. The challenge is to handle multiple snapshots efficiently without scanning the full array each time.

Examples

Example 1

Input: ["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]]

Output: [null,null,0,null,5]

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.

Solution Approach

Use Versioned Lists for Each Index

Maintain a list of (snap_id, value) pairs for each array index. On set, append or update the latest pair; on snap, increment the snap counter. This allows constant-time updates and avoids full array copying.

Binary Search for Efficient Retrieval

For get(index, snap_id), perform a binary search on the versioned list at that index to find the largest snap_id less than or equal to the requested one. This ensures O(log n) lookup and aligns with the array scanning plus hash lookup pattern.

Optimize Memory by Storing Changes Only

Instead of storing the entire array for each snapshot, only store changes at each index. This reduces space complexity and prevents redundant data, crucial for scaling to tens of thousands of operations.

Complexity Analysis

Metric	Value
Time	O(n \log n + k)
Space	O(n + k)

Time complexity is O(n \log n + k), where n is the number of set operations and k is the number of get queries, due to binary search per get. Space complexity is O(n + k) because we only store modified elements per snap rather than full array copies.

What Interviewers Usually Probe

Expectations that each index maintains its own change history to avoid O(n) scanning.
Focus on using binary search to optimize get operations over historical snapshots.
Discussion on trade-offs between memory usage and snapshot speed is important.

Common Pitfalls or Variants

Common pitfalls

Storing full arrays on each snap causes memory overflow for large inputs.
Using linear search in get leads to TLE for many operations.
Forgetting to append initial value (e.g., 0) for all indices before the first snap can produce incorrect results.

Follow-up variants

SnapshotArray with range updates instead of single index updates.
Persistent segment tree approach to maintain snapshot history for large arrays.
Tracking multiple attributes per index, requiring nested versioned lists.

FAQ

What is the primary pattern in SnapshotArray?

The problem uses an array scanning plus hash lookup pattern, where each index stores a history of changes for fast retrieval.

How does get work efficiently in SnapshotArray?

get uses binary search on the versioned list of the target index to locate the most recent value before or at the given snap_id.

Why not copy the whole array on each snap?

Copying the full array each time leads to O(n * snapshots) space, which is inefficient and unnecessary since only changed elements need tracking.

What are the constraints for the SnapshotArray problem?

Array length is up to 5 * 10^4, values up to 10^9, snap_id less than total snaps, and at most 5 * 10^4 calls for set, snap, and get combined.

Can this approach handle thousands of snaps efficiently?

Yes, storing only changes per index and using binary search ensures both time and space efficiency even for tens of thousands of operations.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class SnapshotArray:

    def __init__(self, length: int):
        self.arr = [[] for _ in range(length)]
        self.i = 0

    def set(self, index: int, val: int) -> None:
        self.arr[index].append((self.i, val))

    def snap(self) -> int:
        self.i += 1
        return self.i - 1

    def get(self, index: int, snap_id: int) -> int:
        i = bisect_left(self.arr[index], (snap_id, inf)) - 1
        return 0 if i < 0 else self.arr[index][i][1]


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)

Continue Practicing

#911 online election #1170 compare strings by frequency of the smallest character #1027 longest arithmetic subsequence