Welcome to Subscribe On Youtube

1146. Snapshot Array

Description

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 <= 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.

Solutions

Solution 1: Array + Binary Search

Maintain an array, each element of which is a list storing the values set each time and their corresponding snapshot IDs.

Each time a value is set, add the value and snapshot ID to the list at the corresponding index.

Each time a value is retrieved, use binary search to find the first value in the corresponding position that is greater than the snapshot ID snap_id, and then return the previous value.

In terms of time complexity, the time complexity of setting a value is $O(1)$, the time complexity of a snapshot is $O(1)$, and the time complexity of getting a value is $O(\log n)$.

  • class SnapshotArray {
        private List<int[]>[] arr;
        private int idx;
    
        public SnapshotArray(int length) {
            arr = new List[length];
            Arrays.setAll(arr, k -> new ArrayList<>());
        }
    
        public void set(int index, int val) {
            arr[index].add(new int[] {idx, val});
        }
    
        public int snap() {
            return idx++;
        }
    
        public int get(int index, int snap_id) {
            var vals = arr[index];
            int left = 0, right = vals.size();
            while (left < right) {
                int mid = (left + right) >> 1;
                if (vals.get(mid)[0] > snap_id) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left == 0 ? 0 : vals.get(left - 1)[1];
        }
    }
    
    /**
     * Your SnapshotArray object will be instantiated and called as such:
     * SnapshotArray obj = new SnapshotArray(length);
     * obj.set(index,val);
     * int param_2 = obj.snap();
     * int param_3 = obj.get(index,snap_id);
     */
    
  • class SnapshotArray {
    public:
        SnapshotArray(int length) {
            idx = 0;
            arr = vector<vector<pair<int, int>>>(length);
        }
    
        void set(int index, int val) {
            arr[index].push_back({idx, val});
        }
    
        int snap() {
            return idx++;
        }
    
        int get(int index, int snap_id) {
            auto& vals = arr[index];
            int left = 0, right = vals.size();
            while (left < right) {
                int mid = (left + right) >> 1;
                if (vals[mid].first > snap_id) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left == 0 ? 0 : vals[left - 1].second;
        }
    
    private:
        vector<vector<pair<int, int>>> arr;
        int idx;
    };
    
    /**
     * Your SnapshotArray object will be instantiated and called as such:
     * SnapshotArray* obj = new SnapshotArray(length);
     * obj->set(index,val);
     * int param_2 = obj->snap();
     * int param_3 = obj->get(index,snap_id);
     */
    
  • class SnapshotArray:
        def __init__(self, length: int):
            self.idx = 0
            self.arr = defaultdict(list)
    
        def set(self, index: int, val: int) -> None:
            self.arr[index].append((self.idx, val))
    
        def snap(self) -> int:
            self.idx += 1
            return self.idx - 1
    
        def get(self, index: int, snap_id: int) -> int:
            vals = self.arr[index]
            i = bisect_right(vals, (snap_id, inf)) - 1
            return 0 if i < 0 else vals[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)
    
    
  • type SnapshotArray struct {
    	idx int
    	arr [][]pair
    }
    
    func Constructor(length int) SnapshotArray {
    	return SnapshotArray{0, make([][]pair, length)}
    }
    
    func (this *SnapshotArray) Set(index int, val int) {
    	this.arr[index] = append(this.arr[index], pair{this.idx, val})
    }
    
    func (this *SnapshotArray) Snap() int {
    	this.idx++
    	return this.idx - 1
    }
    
    func (this *SnapshotArray) Get(index int, snap_id int) int {
    	vals := this.arr[index]
    	i := sort.Search(len(vals), func(i int) bool { return vals[i].i > snap_id })
    	if i == 0 {
    		return 0
    	}
    	return vals[i-1].v
    }
    
    type pair struct{ i, v int }
    
    /**
     * 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);
     */
    
  • class SnapshotArray {
        private arr: [number, number][][];
        private i: number = 0;
        constructor(length: number) {
            this.arr = Array.from({ length }, () => []);
        }
    
        set(index: number, val: number): void {
            this.arr[index].push([this.i, val]);
        }
    
        snap(): number {
            return this.i++;
        }
    
        get(index: number, snap_id: number): number {
            let [l, r] = [0, this.arr[index].length];
            while (l < r) {
                const mid = (l + r) >> 1;
                if (this.arr[index][mid][0] > snap_id) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            --l;
            return l < 0 ? 0 : this.arr[index][l][1];
        }
    }
    
    /**
     * Your SnapshotArray object will be instantiated and called as such:
     * var obj = new SnapshotArray(length)
     * obj.set(index,val)
     * var param_2 = obj.snap()
     * var param_3 = obj.get(index,snap_id)
     */
    
    

All Problems

All Solutions