1146.snapshot-array.md

1146. Snapshot Array

Key Insights

The shapshot array is a data structure that supports the following operations:

nums = [0, 0, 0, 0, 0]
        |  |  |
 set    1  3  5
        |  |  |
       [1, 3, 5, 0, 0]  
        |     |         [1, 3, 5, 0, 0] // snapshot 0
        |     |     
 set    7     8
        |     |
       [7, 3, 8, 0, 0]
                        [1, 3, 7, 8, 0] // snapshot 1
// No update
                        [1, 3, 7, 8, 0] // snapshot 2
        |        |
 set    9        2
        |        |
       [9, 3, 8, 2, 0]
                        [9, 3, 8, 2, 0] // snapshot 3

There are some possible scenarios:

• We can set multiple times at the same index, then snapshot:

0 -> set(1) -> set(3) -> set(5) -> snapshot 0

get(snapId=0) = 5

• We can set multiple times at the same index, but no snapshot:

0 -> set(1) -> set(3) -> set(5) -> set(7)

// No get() operation since we didn't take any snapshot

• We can snap multiple times without changing the array:

0 -> set(1) -> snapshot 0 -> snapshot 1 -> snapshot 2

get(snapId=0) = 1
get(snapId=1) = 1
get(snapId=2) = 1

接下来我们需要考虑一个效率的问题。我们每调用一次snap()是否需要给每个元素都新建一次快照呢？显然如果大多数元素都没有更新过的话，再添加一次快照的效率不高。所以我们可以设置一个changed的集合，里面只存放上一次snap()之后变动过的元素，也就是被set()过的元素。 我们会发现对于每个元素而言，它被记录的snapId并不是连续的。所以我们应该在snaps[index]里面找到最后一个小于等于snapId的那个时间戳。

Brute Force (MLE)

We just save all snapshots. It wastes memory if we have a large array but only a few elements are modified.

class SnapshotArray(private val length: Int) {

    private var currentSnapId = 0

    private val array = IntArray(length)
    private val snapshot = mutableListOf<IntArray>()

    fun set(index: Int, `val`: Int) {
        array[index] = `val`
    }

    fun snap(): Int {
        snapshot.add(array.clone())
        return currentSnapId++
    }

    fun get(index: Int, snapId: Int): Int {
        return snapshot[snapId][index]
    }
}

Binary Search

Since we might take multiple snapshots, but only retrieve the value at a specific snapshot, we need an efficient way to store and retrieve the value at a specific snapshot.

Instead of storing all values at every snapshot, we store only when a value is modified. We can use a list of modifications to store the modified records, which maintains a history of (snapId, value) pairs for each element in the array, and we only record the modified elements when set() is called.

// For nums[0]
0 -> set(1) -> snapshot 0 -> set(7) -> snapshot 1 -> ...... -> snapshot 2 -> set(9) -> snapshot 3
0 --------------------> 1 --------------------------------------------> 7 --------------------> 9
                        ^                       ^                       ^                       ^             
                        record(snapId=0, 1)     record(snapId=1, 7)     X                       record(snapId=3, 9)
                                                                 
// Add modification records for nums[0]
record(snapId=0, 1)    // set(1)
record(snapId=1, 7)    // set(7)
record(snapId=3, 9)    // set(9)

// The corresponding get() for nums[0] at different snapshots
get(snapId=0) = 1
get(snapId=1) = 7
get(snapId=2) = 7 // No update, we return the last value = 7 which is from the most latest record: snapId=1
get(snapId=3) = 9

And since shapshot ID are incremental, so all modification records are sorted by snapId. When we call get(), we can binary search the snapshot to find the most recent records, which is the last snapshot <= snapId.

data class Item(
    val snapId: Int,
    val value: Int
)

class SnapshotArray(private val length: Int) {

    private var currentSnapId = 0
    // Space Complexity is `O(n + k)` where `n` is the length of the array and `k` is the number of modifications.
    private val modificationRecords = Array<MutableList<Item>>(length) { mutableListOf() }

    // Time Complexity is `O(1)`
    fun set(index: Int, `val`: Int) {
        // We only record the modification if the value is really changed. (Optional)
        if (modificationRecords[index].lastOrNull()?.value == `val`) return

        modificationRecords[index].add(Item(currentSnapId, `val`))
    }

    // Time Complexity is `O(1)`
    fun snap(): Int {
        return currentSnapId++
    }

    // Time Complexity is `O(log(k))` where `k` is the number of modifications.
    fun get(index: Int, snapId: Int): Int {
        return binarySearch(modificationRecords[index], snapId)
    }

    private fun binarySearch(records: List<Item>, snapId: Int): Int {
        var left = 0
        var right = records.size - 1
        while (left <= right) {
            val middle = left + (right - left) / 2
            if (records[middle].snapId <= snapId) {
                left = middle + 1
            } else if (records[middle].snapId > snapId) {
                right = middle - 1
            }
        }
        // We need to check if not found, we return 0
        return if (right in 0 until records.size) records[right].value else 0
    }
}