Problem statement

https://leetcode.com/problems/snapshot-array/

Solution

For each index, let us keep history of chances: list of tuples with snap_id and val.

  1. __init__(self, length): time complexity is O(n), space complexity as well. We can reduce space complexity if we initialize not list of lists, but dictionary of lists and then when we do binary search we first check if we have element in dictionary or not. Space complexity in this case will be O(1).
  2. set(self, index, val): we just put new pair into our list. We can optimize memory a bit, if we rewrite elements with the same snap_id. Time complexity is O(1).
  3. snap(self), just increase snap_id by one, time complexity is O(1).
  4. get(self, index, snap_id): do binary search in corresponding index, time complexity is O(log m), where m is number of calls of snap.

Complexity

It is discussed in solution already.

Code

class SnapshotArray:
    def __init__(self, length):
        self.snap_id = 0
        self.array = [[(-1,0)] for _ in range(length)] 

    def set(self, index, val):
        self.array[index] += [(self.snap_id, val)]
        
    def snap(self):
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index, snap_id):
        ind = bisect.bisect(self.array[index], (snap_id, float("inf"))) - 1
        return self.array[index][ind][1]