Leetcode 1249 Solution

This article provides solution to leetcode question 1249 (snapshot-array)
Categories:
Tags:
Access this page by simply typing in "lcs 1249" in your browser address bar if you have bunnylol configured.

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

Solution

class SnapshotArray:



    def __init__(self, length: int):
        self.value_lists = [[(0, 0)] for _ in range(length)]
        self.snap_id = 0



    def set(self, index: int, val: int) -> None:
        value_list = self.value_lists[index]



        if value_list[-1][0] == self.snap_id:
            value_list[-1] = (self.snap_id, val)
        else:
            value_list.append((self.snap_id, val))



    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1



    def get(self, index: int, snap_id: int) -> int:
        value_list = self.value_lists[index]



        l = 0
        r = len(value_list) - 1



        while l < r:
            m = (l + r + 1) // 2



            if value_list[m][0] > snap_id:
                r = m - 1
            else:
                l = m



        return value_list[l][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)