LeetCode: Snapshot Array

Snapshot Array

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #linkedlist

Implement a SnapshotArray that supports the following interface:

• SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
• void set(index, val) sets the element at the given index to be equal to val.
• int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
• int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
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 <= 50000
• At most 50000 calls will be made to set, snap, and get.
• 0 <= index < length
• 0 <= snap_id < (the total number of times we call snap())
• 0 <= val <= 10^9

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

// https://code.dennyzhang.com/snapshot-array
// Basic Ideas:
//
// Complexity:
type SnapshotArray struct {
    m map[int]map[int]int
    cur_id int
}

func Constructor(length int) SnapshotArray {
    cur_id := 0
    m := map[int]map[int]int{}
    m[0] = map[int]int{}
    return SnapshotArray{m, cur_id}
}

func (this *SnapshotArray) Set(index int, val int)  {
    this.m[this.cur_id][index] = val
}

func (this *SnapshotArray) Snap() int {
    this.cur_id++
    this.m[this.cur_id] = map[int]int{}
    return this.cur_id-1
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
    for i:=snap_id; i>=0; i-- {
        v, ok := this.m[i][index]
        if ok { return v }
    }
    return 0
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * obj := Constructor(length);
 * obj.Set(index,val);
 * param_2 := obj.Snap();
 * param_3 := obj.Get(index,snap_id);
 */