How do I reduce amount of memory used here?

May 24, 2024

So, I wrote a code, for this problem.

Code :

import copy

class SnapshotArray:

    def __init__(self, length: int):
        self.lst = [0] * length
        self.snap_id = -1
        self.hash = []
        self.by_snap_id = 0
        return None

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

    def snap(self) -> int:
        self.snap_id += 1
        self.copy = copy.copy(self.lst)
        self.hash.append(self.copy)
        del self.lst
        self.lst = self.hash[self.snap_id]
        return self.snap_id

    def get(self, index: int, snap_id: int) -> int:
        return self.hash[snap_id][index]

In 69 / 75 testcase it says MLE

So I tried to make just one list from which I’ll be taking value for current list too, but it didn’t work. So, how do I reduce amount of memory used?

>Solution :

Probably the issue is you storing multiple copies of the entire list. To optimize memory usage store only the changes made btw snapshots:

class SnapshotArray:

def __init__(self, length: int):
    self.snapshots = [{}] 
    self.current = {}
    self.snap_id = 0
def set(self, index: int, val: int) -> None:
    self.current[index] = val
def snap(self) -> int:
    self.snapshots.append(self.current.copy())
    self.current = {}
    self.snap_id += 1
    return self.snap_id - 1
def get(self, index: int, snap_id: int) -> int:
    for i in range(snap_id, -1, -1):
        if index in self.snapshots[i]:
            return self.snapshots[i][index]
    return 0