1146. Snapshot Array

class SnapshotArray:
    """
    main idea: avoid redundent array copy in other unchanged indexes, use a list to record each snap_id's value according to each index;  use Binary Search to lookup history snap_id and its corresponding value  
    """
    # tc O(N)  sc O(N)
    def __init__(self, n: int):
        self.snap_id = 0 
        self.idx_idval = {i:[(0,0)] for i in range(n)} # idx: [[snap_id:val],....]
    
    #  tc O(1) 
    def set(self, index: int, val: int) -> None:
        if self.snap_id == self.idx_idval[index][-1][0]:
            self.idx_idval[index][-1] = [self.snap_id,val]
        else:
            self.idx_idval[index].append((self.snap_id,val))            

    def snap(self) -> int:
        self.snap_id += 1 
        return self.snap_id - 1 
        
    #  tc O(lgS * M)  S: number of snap calls;  M: number of get calls 
    def get(self, index: int, snap_id: int) -> int:
        A = self.idx_idval[index]
        idx = bisect.bisect_left(A,(snap_id,)) # search for [snap_id] if using [snap_id,val] as unit  in A 
        #print(A,idx)
        if idx >= len(A):
            return A[-1][1]
        else:
            return A[idx][1] if A[idx][0] == snap_id else A[idx-1][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)