LeetCode 1146 - Snapshot Array

The problem asks us to implement a SnapshotArray, a data structure that behaves like an array but also allows taking snapshots of its state at any moment and retrieving the value of any element at a specific snapshot.

leetcodemediumarrayhash-tablebinary-searchdesign

LeetCode Problem 1146

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Design

Solution

Problem Understanding

The problem asks us to implement a SnapshotArray, a data structure that behaves like an array but also allows taking snapshots of its state at any moment and retrieving the value of any element at a specific snapshot. Specifically, the data structure needs to support three operations: set(index, val), snap(), and get(index, snap_id). Initially, all elements of the array are zero. When we call snap(), it returns a unique snap_id that identifies the current state of the array. Later, get(index, snap_id) allows us to query what the value at that index was when that snapshot was taken.

The input represents commands and arguments for the SnapshotArray. The output represents either a snap_id (for snap) or the value at a particular index at a particular snapshot (for get). The constraints tell us that the array can be fairly large (up to 50,000 elements) and that the number of operations can also be up to 50,000. This implies that a naive solution that stores a complete copy of the array for every snapshot would be too slow and memory-intensive.

Important edge cases include multiple set operations on the same index before a snap, get calls for snapshots that have no changes at the queried index, and querying the very first snapshot. The problem guarantees valid indices and snap_ids, so we do not need to handle out-of-bounds errors.

Approaches

The brute-force approach would involve storing a full copy of the array every time snap() is called. This guarantees correctness because we can directly return the value for any index in any snapshot, but it is prohibitively slow and consumes O(n * m) memory, where n is the array length and m is the number of snaps. For the maximum constraints, this could use billions of integers in memory.

The optimal solution leverages the observation that most elements do not change between consecutive snapshots. Instead of storing the full array for each snapshot, we can store a history of changes for each index. We maintain a list of (snap_id, value) pairs for each index. When get is called, we perform a binary search in the list of changes for the largest snap_id not exceeding the requested one. This reduces memory usage and allows efficient retrieval.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per snap, O(1) per get O(n * m) Stores full array for each snapshot
Optimal O(log s) per get, O(1) per set/snap O(n + k) Stores only changes per index; uses binary search for queries

Here, s is the number of snapshots for a specific index, and k is the total number of changes.

Algorithm Walkthrough

  1. Initialize a list of lists, where each element corresponds to an index in the array. Each index contains a list of (snap_id, value) pairs. Initially, all lists contain (0, 0) to represent the starting value.
  2. Maintain a current_snap_id counter starting at 0. This counter increases by 1 every time snap() is called.
  3. For set(index, val), append (current_snap_id, val) to the list for that index, but only if the last recorded snap_id is not the same as current_snap_id to avoid duplicate entries.
  4. For snap(), return the current snap_id and increment the counter by 1.
  5. For get(index, snap_id), perform a binary search in the list of changes for the specified index to find the largest snap_id that is less than or equal to the requested snap_id. Return the corresponding value.

This approach works because the list of (snap_id, value) pairs for each index is always sorted by snap_id. By storing only changes, we reduce memory usage significantly. Binary search guarantees O(log s) lookup for each get.

Python Solution

from bisect import bisect_right

class SnapshotArray:

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

    def set(self, index: int, val: int) -> None:
        if self.data[index][-1][0] == self.snap_id:
            self.data[index][-1] = (self.snap_id, val)
        else:
            self.data[index].append((self.snap_id, val))

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

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        i = bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

In this implementation, data stores the history of each index. The set method avoids duplicate entries for the same snap_id. The snap method returns the current snap_id and increments it. The get method uses bisect_right to efficiently locate the correct snapshot.

Go Solution

import "sort"

type pair struct {
    snapID int
    val    int
}

type SnapshotArray struct {
    data   [][]pair
    snapID int
}

func Constructor(length int) SnapshotArray {
    data := make([][]pair, length)
    for i := 0; i < length; i++ {
        data[i] = []pair{{0, 0}}
    }
    return SnapshotArray{data: data, snapID: 0}
}

func (this *SnapshotArray) Set(index int, val int) {
    arr := this.data[index]
    if arr[len(arr)-1].snapID == this.snapID {
        arr[len(arr)-1].val = val
    } else {
        this.data[index] = append(arr, pair{this.snapID, val})
    }
}

func (this *SnapshotArray) Snap() int {
    current := this.snapID
    this.snapID++
    return current
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
    arr := this.data[index]
    i := sort.Search(len(arr), func(i int) bool { return arr[i].snapID > snap_id })
    return arr[i-1].val
}

In Go, we use a pair struct to store (snapID, val) for each index. sort.Search is the equivalent of Python's bisect_right. We handle slices carefully, ensuring we do not modify existing snapshots.

Worked Examples

For the input ["SnapshotArray","set","snap","set","get"] with arguments [[3],[0,5],[],[0,6],[0,0]]:

Operation snap_id data state
SnapshotArray(3) 0 [[(0,0)], [(0,0)], [(0,0)]]
set(0,5) 0 [[(0,5)], [(0,0)], [(0,0)]]
snap() 0 [[(0,5)], [(0,0)], [(0,0)]]
set(0,6) 1 [[(0,5),(1,6)], [(0,0)], [(0,0)]]
get(0,0) 0 returns 5 (largest snap_id ≤ 0 for index 0 is 0)

Complexity Analysis

Measure Complexity Explanation
Time O(log s) per get, O(1) per set/snap Binary search on change list for get; set and snap are constant
Space O(n + k) Store initial state plus all changes; n is array length, k is total number of set operations

The reasoning is that each index only stores changes, not full arrays. Binary search ensures efficient lookups.

Test Cases

# Basic example
obj = SnapshotArray(3)
obj.set(0,5)
assert obj.snap() == 0  # snap_id = 0
obj.set(0,6)
assert obj.get(0,0) == 5  # value before second set

# Multiple sets before snap
obj = SnapshotArray(2)
obj.set(1,2)
obj.set(1,3)
assert obj.snap() == 0
assert obj.get(1,0) == 3

# No set before snap
obj = SnapshotArray(1)
assert obj.snap() == 0
assert obj.get(0,0) == 0

# Large values
obj = SnapshotArray(1)
obj.set(0,10**9)
assert obj.snap() == 0
assert obj.get(0,0) == 10**9

# Multiple snapshots
obj = SnapshotArray(1)
obj.set(0,1)
assert obj.snap() == 0
obj.set(0,2)
assert obj.snap() == 1
assert obj.get(0,0) == 1
assert obj.get(0,1) == 2
Test Why
Basic example Validates standard operation
Multiple sets before snap Ensures last set before snap is recorded
No set before snap Checks default zero initialization
Large values Confirms support for max integer values
Multiple snapshots Verifies history retrieval across