Day 7 | 3/20/20

[tech-cow]

• 1146. Snapshot Array

[tech-cow]

1146. Snapshot Array

Brute Force | Memory Limit Exceeded

Memory usage needs to be more efficient. In this code snippet, too many unused 0 element were stored in the dictionary value. Instead, only store used index and value. A nested dictionary does the trick

class SnapshotArray(object):

    def __init__(self, length):
        self.length = length
        self.arr = [0] * self.length
        self.snap_id = -1
        self.dic = {}
        

    def set(self, index, val):
        if index >= 0 and index < len(self.arr):
            self.arr[index] = val

    def snap(self):
        self.snap_id += 1
        self.dic[self.snap_id] = self.arr[:]
        return self.snap_id
        

    def get(self, index, snap_id):
        if snap_id in self.dic:
            return self.dic[snap_id][index]

Hashmap + Deepcopy

This code snippet still duplicates previous snap_array, thus create redundency in elements. for example:

Instead of making a copy to all elements, we only need to make new copies of the elements that has been modified.
For the remaining unchanged elements, we can query them by a backward while loop, which increase the time complexity back to O(N)

However the time complexity is GREAT

set() O(1)
set() O(1)
get() O(1)

from collections import defaultdict
class SnapshotArray(object):
    def __init__(self, length):
        self.dic = defaultdict(dict)
        self.snap_id = 0
        
        
    def set(self, index, val):
        self.dic[self.snap_id][index] = val
        

    def snap(self):
        self.snap_id += 1
        self.dic[self.snap_id] = self.dic[self.snap_id - 1].copy()
        return self.snap_id -1
        

    def get(self, index, snap_id):
        if index in self.dic[snap_id]:
            return self.dic[snap_id][index]
        else:
            return 0

Backward While Loop

We can make this search faster by replacing linear query with a binary search

from collections import defaultdict
class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.history = defaultdict(dict)
    
    def set(self, index: int, val: int) -> None:
        self.history[self.snap_id][index] = val
    
    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1
    
    def get(self, index: int, snap_id: int) -> int:
        copy_id = snap_id
        while copy_id > 0 and index not in self.history[copy_id]:
            copy_id -= 1
        if index in self.history[copy_id]:
            return self.history[copy_id][index]
        return 0

Backward Binary Search

Code Snippet from @lee215

    def __init__(self, n):
        self.A = [[[-1, 0]] for _ in xrange(n)]
        self.snap_id = 0

    def set(self, index, val):
        self.A[index].append([self.snap_id, val])

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

    def get(self, index, snap_id):
        i = bisect.bisect(self.A[index], [snap_id + 1]) - 1
        return self.A[index][i][1]