1146. Snapshot Array

Snapshot Array (LeetCode 1146) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

How to solve Snapshot Array

Snapshot Array is a Data Structure Design problem, part of Design Patterns. Design and implement data structures: LRU cache, LFU cache, HashMap, and specialized structures.

Work towards the solution in these steps:

1. Use a list of lists, adding both the element and the snap_id to each index.

The reference solution runs in O(log S) time and O(N + Q) space.

The Snapshot Array solution and editorial walks through the full approach with reference code.

Problem statement

Implement a SnapshotArray that supports the following interface:

- SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.

- void set(index, val) sets the element at the given index to be equal to val.

- int snap() takes a snapshot of the array and returns the snapid: the total number of times we called snap() minus 1.

- int get(index, snapid) returns the value at the given index, at the time we took the snapshot with the given snapid

Example 1:

Input: ["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]] Output: [null,null,0,null,5] Explanation: SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3 snapshotArr.set(0,5); // Set array[0] = 5 snapshotArr.snap(); // Take a snapshot, return snapid = 0 snapshotArr.set(0,6); snapshotArr.get(0,0); // Get the value of array[0] with snapid = 0, return 5

Constraints:

- 1 <= length <= 5 104

- 0 <= index < length

- 0 <= val <= 109

- 0 <= snapid < (the total number of times we call snap())

- At most 5 104 calls will be made to set, snap, and get.

Topics and companies

Topics: Array, Hash Table, Binary Search, Design.

Reported in interviews at Google, Rubrik.

How to practise Snapshot Array on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(log S) time and O(N + Q) space.

Open Snapshot Array in the code editor, or read the Snapshot Array editorial for a worked solution with its approach and complexity analysis.

Where Snapshot Array sits in the DSA pattern sheet

• Design Patterns pattern guide
• Design (General/Specific) subpattern
• The full DSA patterns sheet

Problems related to Snapshot Array

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

• All O`one Data Structure — Hard, same subpattern
• Design a Stack With Increment Operation — Medium, same subpattern
• Design a Text Editor — Hard, same subpattern
• Design Circular Deque — Medium, same subpattern
• Design Circular Queue — Medium, same subpattern
• Design Compressed String Iterator — Easy, same subpattern

Snapshot Array FAQ