Skip to main content
CodePeet

CodePeet 700 Complete DSA Sheet

Snapshot Array

Try it yourself
MediumProblemExternal link

Description

Implement a SnapshotArray, an array that can take snapshots of itself and read any cell as it was at any of them:

  • SnapshotArray(int length) starts an array of length cells, each 0.
  • void set(int index, int val) sets the cell at index to val.
  • int snap() takes a snapshot and returns its id, the number of times snap() was called before it.
  • int get(int index, int snap_id) returns the value the cell at index had when the snapshot with id snap_id was taken.

Examples

Example 1

Input:

["SnapshotArray", "set", "snap", "set", "get"]
[[3], [0, 5], [], [0, 6], [0, 0]]

Output: [null, null, 0, null, 5]

Explanation: Cell 0 is 5 when snapshot 0 is taken; setting it to 6 afterwards doesn't change what snapshot 0 saw, so get(0, 0) is 5.

Example 2

Input:

["SnapshotArray", "set", "set", "snap", "get", "set", "snap", "get", "get"]
[[2], [1, 4], [1, 8], [], [1, 0], [0, 3], [], [0, 0], [1, 1]]

Output: [null, null, null, 0, 8, null, 1, 0, 8]

Explanation: Cell 1 is set twice before snapshot 0, and only the 8 counts. Cell 0 gets 3 only after snapshot 0, so at snapshot 0 it was still 0. At snapshot 1, cell 1 hadn't changed since snapshot 0: still 8.

Example 3

Input:

["SnapshotArray", "snap", "snap", "set", "snap", "get", "get", "get"]
[[1], [], [], [0, 9], [], [0, 0], [0, 1], [0, 2]]

Output: [null, 0, 1, null, 2, 0, 0, 9]

Explanation: Two snapshots with nothing changed hand out ids 0 and 1. The 9 is set before snapshot 2, so only snapshot 2 sees it.

Constraints

  • 1 ≤ length ≤ 5 × 10⁴
  • 0 ≤ index < length
  • 0 ≤ val ≤ 10⁹
  • 0 ≤ snap_id < the number of times snap() has been called
  • At most 5 × 10⁴ calls are made to set, snap and get

Editorial

Brute Force

Intuition

Keep the array as it is, and on every snap store a full copy of it. A read looks the cell up in that snapshot's copy.

Step-by-Step Explanation

Let's trace Example 2:

  1. set(1, 4) writes 4 into cell 1 of the array.
  2. set(1, 8) writes 8 into cell 1 of the array.
  3. snap() copies the whole array, 2 cells, changed or not, as snapshot 0, and returns 0.
  4. get(1, 0) reads cell 1 of snapshot 0's copy, which holds 8.
  5. set(0, 3) writes 3 into cell 0 of the array.
  6. snap() copies the whole array, 2 cells, changed or not, as snapshot 1, and returns 1.
  7. get(0, 0) reads cell 0 of snapshot 0's copy, still 0 then.
  8. get(1, 1) reads cell 1 of snapshot 1's copy, which holds 8.

A Copy per Snapshot — Each snap stores a copy of every cell above the array; a read looks in one copy.

Algorithm

  1. Keep the array, length cells of 0, and a list of copies.
  2. set writes val into the array.
  3. snap appends a copy of the whole array and returns its index in the list.
  4. get returns the cell at index in the copy at snap_id.

Code

class SnapshotArray {
    vector<int> cells;
    vector<vector<int>> snaps;                // a full copy of the array per snap
public:
    SnapshotArray(int length) : cells(length, 0) {
    }

    void set(int index, int val) {
        cells[index] = val;
    }

    int snap() {
        snaps.push_back(cells);               // every cell, changed or not
        return snaps.size() - 1;
    }

    int get(int index, int snap_id) {
        return snaps[snap_id][index];
    }
};

class SnapshotArray:
    def __init__(self, length: int):
        self.cells = [0] * length
        self.snaps = []                       # a full copy of the array per snap

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

    def snap(self) -> int:
        self.snaps.append(self.cells[:])      # every cell, changed or not
        return len(self.snaps) - 1

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

class SnapshotArray {
    private final int[] cells;
    private final List<int[]> snaps = new ArrayList<>();   // a full copy of the array per snap

    public SnapshotArray(int length) {
        cells = new int[length];
    }

    public void set(int index, int val) {
        cells[index] = val;
    }

    public int snap() {
        snaps.add(cells.clone());                           // every cell, changed or not
        return snaps.size() - 1;
    }

    public int get(int index, int snap_id) {
        return snaps.get(snap_id)[index];
    }
}

var SnapshotArray = function(length) {
    this.cells = new Array(length).fill(0);
    this.snaps = [];                          // a full copy of the array per snap
};

SnapshotArray.prototype.set = function(index, val) {
    this.cells[index] = val;
};

SnapshotArray.prototype.snap = function() {
    this.snaps.push(this.cells.slice());      // every cell, changed or not
    return this.snaps.length - 1;
};

SnapshotArray.prototype.get = function(index, snap_id) {
    return this.snaps[snap_id][index];
};

Complexity Analysis

Time Complexity: O(1) for set and get, O(length) for snap

Each snap copies every cell.

Space Complexity: O(snaps × length)

One full copy of the array per snapshot.

Why This Approach Is Not Efficient

A copy stores every cell again, changed or not. On the largest tests, 2 × 10⁴ snaps of 5 × 10⁴ cells, the copies would hold 10⁹ values, and on the judge it ran out of memory in C++, Python, Java and JavaScript. Yet between two snaps most cells don't change; in those tests only one does. Keep, for each cell, only its changes and the snap each was made in.

Optimal Approach - A History per Cell

Intuition

Each cell keeps a list of (snap id, value) for the snaps it changed in. A set writes into the current snap: a new entry, or, when the cell has already changed in this snap, a replacement of its last one, since only the value at snap time counts. snap() hands out the current id and moves on, copying nothing. The entries are in snap order, so get(index, snap_id) is a binary search for the last one at or before snap_id, and a cell with no change by then is still 0.

Step-by-Step Explanation

Let's trace Example 2 again:

  1. set(1, 4): cell 1 gets a new change, (0, 4).
  2. set(1, 8): cell 1 already changed in snap 0, so 8 replaces 4 in its last change.
  3. snap() returns 0, and sets from now on go into snap 1. Nothing is copied.
  4. get(1, 0): the binary search on cell 1's changes finds (0, 8), the last one at or before snap 0, so the answer is 8.
  5. set(0, 3): cell 0 gets a new change, (1, 3).
  6. snap() returns 1, and sets from now on go into snap 2. Nothing is copied.
  7. get(0, 0): cell 0 has no change at or before snap 0, so it still held 0.
  8. get(1, 1): the binary search on cell 1's changes finds (0, 8), the last one at or before snap 1, so the answer is 8.

A History per Cell — One row per cell, its changes in snap order; a read finds the last one at or before its snap.

Algorithm

  1. Keep, per cell, a list of snap ids and a list of values, and the current snap id, starting at 0.
  2. set: if the cell's last change was made in the current snap, replace its value; otherwise append (current snap id, val).
  3. snap: return the current snap id and add 1 to it.
  4. get: binary search the cell's snap ids for the last one at or before snap_id, bisect_right(ids, snap_id) - 1; return its value, or 0 if there is none.

Code

class SnapshotArray {
    vector<vector<int>> snapIds, values;      // each cell's changes: the snap they were made in, and the value
    int snapId = 0;
public:
    SnapshotArray(int length) : snapIds(length), values(length) {
    }

    void set(int index, int val) {
        auto &ids = snapIds[index], &vals = values[index];
        if (!ids.empty() && ids.back() == snapId) vals.back() = val;   // changed already in this snap: the later value wins
        else {
            ids.push_back(snapId);
            vals.push_back(val);
        }
    }

    int snap() {
        return snapId++;
    }

    int get(int index, int snapId) {
        auto& ids = snapIds[index];
        int i = upper_bound(ids.begin(), ids.end(), snapId) - ids.begin() - 1;   // the last change at or before snapId
        return i >= 0 ? values[index][i] : 0;
    }
};

import bisect


class SnapshotArray:
    def __init__(self, length: int):
        self.snap_ids = [[] for _ in range(length)]   # each cell's changes: the snap they were made in
        self.values = [[] for _ in range(length)]     # and the value
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        ids, vals = self.snap_ids[index], self.values[index]
        if ids and ids[-1] == self.snap_id:           # changed already in this snap: the later value wins
            vals[-1] = val
        else:
            ids.append(self.snap_id)
            vals.append(val)

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

    def get(self, index: int, snap_id: int) -> int:
        i = bisect.bisect_right(self.snap_ids[index], snap_id) - 1   # the last change at or before snap_id
        return self.values[index][i] if i >= 0 else 0

class SnapshotArray {
    private final List<List<Integer>> snapIds = new ArrayList<>(), values = new ArrayList<>();   // each cell's changes
    private int snapId = 0;

    public SnapshotArray(int length) {
        for (int i = 0; i < length; i++) {
            snapIds.add(new ArrayList<>());
            values.add(new ArrayList<>());
        }
    }

    public void set(int index, int val) {
        List<Integer> ids = snapIds.get(index), vals = values.get(index);
        if (!ids.isEmpty() && ids.get(ids.size() - 1) == snapId) vals.set(vals.size() - 1, val);   // the later value wins
        else {
            ids.add(snapId);
            vals.add(val);
        }
    }

    public int snap() {
        return snapId++;
    }

    public int get(int index, int snapId) {
        List<Integer> ids = snapIds.get(index);
        int lo = 0, hi = ids.size();                  // the first change after snapId
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (ids.get(mid) <= snapId) lo = mid + 1;
            else hi = mid;
        }
        return lo > 0 ? values.get(index).get(lo - 1) : 0;   // the one before it is the last at or before
    }
}

class SnapshotArray {
    constructor(length) {
        this.snapIds = Array.from({ length }, () => []);   // each cell's changes: the snap they were made in
        this.values = Array.from({ length }, () => []);    // and the value
        this.snapId = 0;
    }

    set(index, val) {
        const ids = this.snapIds[index], vals = this.values[index];
        if (ids.length && ids[ids.length - 1] === this.snapId) vals[vals.length - 1] = val;   // the later value wins
        else {
            ids.push(this.snapId);
            vals.push(val);
        }
    }

    snap() {
        return this.snapId++;
    }

    get(index, snapId) {
        const ids = this.snapIds[index];
        let lo = 0, hi = ids.length;          // the first change after snapId
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (ids[mid] <= snapId) lo = mid + 1;
            else hi = mid;
        }
        return lo > 0 ? this.values[index][lo - 1] : 0;   // the one before it is the last at or before
    }
}

Complexity Analysis

Time Complexity: O(1) for set and snap, O(log c) for get

set and snap touch one entry or one counter; get searches the c changes of one cell.

Space Complexity: O(length + sets)

One empty list per cell, and at most one entry per set.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Reading the change before the snap. bisect.bisect_left

On Example 3 it returns [null, 0, 1, null, 2, 0, 0, 0]; the answer is [null, 0, 1, null, 2, 0, 0, 9]. A change made in snap s is what snap s saw, so the read wants the last change at or before snap_id. bisect_left finds the first change at or after it, and one step back from there skips a change made in that very snap.

snap() handing out the next id. return self.snap_id

On Example 2 it returns [null, null, null, 1, 8, null, 2, 0, 8]; the answer is [null, null, null, 0, 8, null, 1, 0, 8]. snap() returns the id of the snapshot it just took, the snap the sets so far were made in. Returning the counter after moving it on gives 1 for the first snapshot instead of 0.

Writing over an older snap's change. if ids:

On Example 1 it returns [null, null, 0, null, 6]; the answer is [null, null, 0, null, 5]. Only a set in the same snap may replace the cell's last change. A change from an older snap belongs to that snapshot; writing over it rewrites what the snapshot saw.

Where This Pattern Is Taught

This problem practises keeping each cell's changes with the snap they were made in, and reading the past with a binary search. It's taught in Designing with History.