2349. Design a Number Container System

MediumDesignHash TableOrdered SetHeap (Priority Queue)
Leetcode Link

Problem Description

The LeetCode problem entails designing a system that can manage a set of numbers each located at a unique index. The system needs to support two primary operations:

  1. change: This operation must insert or replace a number at a specified index. If an index already contains a number, it should be replaced with the new number.

  2. find: This operation should return the smallest index at which a specific number is located. If the number is not present in any container, the system should return -1.

The challenge is to implement these operations efficiently, meaning we need to optimize for both insert/replace and search operations, ensuring that find queries are performed in an optimized manner, especially in a dataset where searches are frequent compared to updates.

Intuition

To arrive at the solution, we need a data structure that can efficiently keep track of each number's indices and quickly retrieve the smallest index of any given number. We use two main data structures to achieve this:

  1. A hash map (self.mp), where the key is the index and the value is the number at that index. This allows us to quickly check if an index already has a number and to update the number at any index.

  2. A default dictionary of SortedSet (self.t), indexed by numbers. SortedSet is a data structure that maintains the elements in sorted order. This allows us to quickly retrieve the smallest index for a given number as it will always be the first element.

When we perform the change operation, we update the index's number in the hash map. If the index already had a number, we remove the index from the SortedSet of that old number. Then we add the index to the SortedSet of the new number.

During the find operation, we look up the SortedSet for the given number. If the SortedSet is not empty, we return the first element (since it's the smallest index due to the properties of the SortedSet). If the SortedSet is empty, it means the number is not present at any index, so we return -1.

This approach allows us to efficiently update the indices and retrieve the smallest index for any number, making the NumberContainers class a fast and reliable system for the operations required.

Learn more about Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation of the NumberContainers class uses a hash map and a default dictionary of SortedSet structures. The SortedSet is chosen for its properties of maintaining the elements in sorted order, which is essential for efficient retrieval of indices.

Here's a step-by-step breakdown of the implementation:

  1. Initialization (__init__ method):

    • A hash map self.mp is initialized to keep track of which number is at which index.
    • A default dictionary self.t of SortedSet is initialized to store sets of indices for each number. The defaultdict from the Python collections module ensures that each number key in the dictionary will automatically be associated with an empty SortedSet if it does not already exist in the dictionary.
  2. Change operation (change method):

    • Given an index and a number:
      • If the index already exists in the hash map (indicating a number is already present at that index), remove the index from the SortedSet of the current number associated with that index.
      • Update the hash map with the new number at the index.
      • Add the index to the SortedSet of the new number. This operation automatically keeps the SortedSet in sorted order.

    Python code snippet for the change operation:

    1def change(self, index: int, number: int) -> None:
    2    if index in self.mp:
    3        v = self.mp[index]
    4        self.t[v].remove(index)
    5    self.mp[index] = number
    6    self.t[number].add(index)
  3. Find operation (find method):

    • To find the smallest index for a given number:
      • Retrieve the SortedSet associated with the number from self.t.
      • If the SortedSet is not empty, return the first element (smallest index) since the indices are maintained in sorted order.
      • If the SortedSet is empty, return -1 indicating the number is not present at any index.

    Python code snippet for the find operation:

    1def find(self, number: int) -> int:
    2    s = self.t[number]
    3    return s[0] if s else -1

The choice of SortedSet is crucial for the solution's efficiency. SortedSet allows for fast addition and removal of index elements while maintaining a sort order, making the find operation a simple and quick retrieval of the smallest element. This solution thus capably balances the need for dynamic updates with frequent and fast queries, delivering the functionalities required by the NumberContainers system.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we initialize our NumberContainers class and the following operations are performed sequentially:

  1. change(2, 1): We want to insert number 1 at index 2.

    • Since index 2 is not yet mapped, we simply insert it into self.mp: self.mp becomes {2: 1}.
    • We add the index to the SortedSet of number 1 in self.t: self.t[1] now contains {2}.
  2. change(1, 1): Now, we insert number 1 at index 1.

    • We add the new key-value pair to self.mp: self.mp becomes {2: 1, 1: 1}.
    • Index 1 is added into the SortedSet of number 1 in self.t: self.t[1] now contains {1, 2}, automatically sorted.
  3. change(2, 2): Number 2 is now inserted at index 2, which already has a number 1.

    • We remove index 2 from the SortedSet of the old number, self.t[1], which then becomes {1}.
    • self.mp is updated to reflect the change: self.mp becomes {2: 2, 1: 1}.
    • Index 2 is added to the SortedSet of number 2 (which was an empty SortedSet before): self.t[2] now contains {2}.
  4. find(1): We want to find the smallest index where number 1 is located.

    • Lookup self.t[1], which contains {1}.
    • The smallest index in the sorted set is the first element, which is 1, thus we return 1.
  5. find(3): We want to find the smallest index where number 3 is located.

    • Since number 3 has never been inserted, self.t[3] is an empty SortedSet.
    • We return -1, indicating that number 3 is not present at any index.

The sequence of these operations would result in the following internal states for our NumberContainers class:

  • Hash map of index to numbers: self.mp = {1: 1, 2: 2}
  • Default dictionary of number to SortedSets of indices: self.t = {1: SortedSet([1]), 2: SortedSet([2])}

This example demonstrates how each change and find operation works as expected, providing efficient updates and lookups as per the problem requirements.

Not Sure What to Study? Take the 2-min Quiz:

Which technique can we use to find the middle of a linked list?

Python Solution

1# Import the defaultdict from collections and SortedSet from sortedcontainers
2from collections import defaultdict
3from sortedcontainers import SortedSet
4
5class NumberContainers:
6    def __init__(self):
7        # Dictionary to hold the current number at each index
8        self.index_to_number = {}
9        # Defaultdict to hold SortedSets which will contain indices for each number
10        # SortedSets are used for maintaining the indices in sorted order
11        self.number_to_indices = defaultdict(SortedSet)
12
13    def change(self, index: int, number: int) -> None:
14        """Update the number at the given index and maintain the indices sorted."""
15        # If the index is already in our mapping, remove it from the current number's SortedSet
16        if index in self.index_to_number:
17            current_number = self.index_to_number[index]
18            self.number_to_indices[current_number].remove(index)
19      
20        # Update the number at the index in our index_to_number mapping
21        self.index_to_number[index] = number
22        # Add the index to the new number's SortedSet
23        self.number_to_indices[number].add(index)
24
25    def find(self, number: int) -> int:
26        """Returns the smallest index for the given number; if not found, returns -1."""
27        # Get the SortedSet of indices for the given number
28        indices = self.number_to_indices[number]
29        # If there are any indices, return the smallest one (first element)
30        # If not, return -1 indicating the number is not assigned to any index
31        return indices[0] if indices else -1
32
33# The NumberContainers class can now be instantiated and methods called as described.
34# obj = NumberContainers()
35# obj.change(index, number)
36# param_2 = obj.find(number)
37

Java Solution

1import java.util.HashMap;
2import java.util.Map;
3import java.util.TreeSet;
4
5class NumberContainers {
6    private final Map<Integer, Integer> indexToNumberMap = new HashMap<>();
7    private final Map<Integer, TreeSet<Integer>> numberToIndicesMap = new HashMap<>();
8
9    // Constructor
10    public NumberContainers() {
11        // Intentionally left blank, no initialization needed here
12    }
13
14    /**
15     * Updates the number at a given index and maintains the mapping of numbers to a sorted set of indices.
16     *
17     * @param index  The index to change.
18     * @param number The new number to associate with the index.
19     */
20    public void change(int index, int number) {
21        // If index already contains a number, update the mapping
22        if (indexToNumberMap.containsKey(index)) {
23            int currentNumber = indexToNumberMap.get(index);
24            // Remove the index from the current number's set
25            TreeSet<Integer> indicesSet = numberToIndicesMap.get(currentNumber);
26            indicesSet.remove(index);
27            // If the set is empty after removal, remove it from the map
28            if (indicesSet.isEmpty()) {
29                numberToIndicesMap.remove(currentNumber);
30            }
31        }
32        // Add or update the index-to-number mapping
33        indexToNumberMap.put(index, number);
34        // Add index to the new number's set, creating the set if it doesn't exist
35        numberToIndicesMap.computeIfAbsent(number, k -> new TreeSet<>()).add(index);
36    }
37
38    /**
39     * Finds the lowest index for a number.
40     * If the number is not associated with any index, returns -1.
41     *
42     * @param number The number to find the lowest index for.
43     * @return The lowest index of the given number or -1 if not found.
44     */
45    public int find(int number) {
46        // Check if number exists in the map and return the first (lowest) index
47        return numberToIndicesMap.containsKey(number) ? numberToIndicesMap.get(number).first() : -1;
48    }
49}
50
51// The NumberContainers object usage remains the same; example of instantiation and method calls:
52// NumberContainers obj = new NumberContainers();
53// obj.change(index,number);
54// int lowestIndex = obj.find(number);
55

C++ Solution

1#include <map>
2#include <set>
3
4class NumberContainers {
5public:
6    // Maps each index to the number it contains.
7    std::map<int, int> indexToNumberMap;
8
9    // Maps each number to a set of indices that contain this number.
10    std::map<int, std::set<int>> numberToIndicesMap;
11
12    // Default constructor.
13    NumberContainers() {
14    }
15
16    // Changes the number at the given index.
17    void change(int index, int number) {
18        // Check if the index is already in the map.
19        auto it = indexToNumberMap.find(index);
20        if (it != indexToNumberMap.end()) {
21            // If the index is already there, remove the index from the set corresponding
22            // to its current number, as it's about to be reassigned.
23            numberToIndicesMap[it->second].erase(index);
24            // Update the index to the new number.
25            it->second = number;
26        } else {
27            // If the index is new, just add it to the map.
28            indexToNumberMap[index] = number;
29        }
30        // Insert the index to the set corresponding to the new number.
31        numberToIndicesMap[number].insert(index);
32    }
33
34    // Finds the smallest index that contains the given number. Returns -1 if such an index cannot be found.
35    int find(int number) {
36        // Attempt to find the set of indices for the given number.
37        auto it = numberToIndicesMap.find(number);
38        // If the number is not found or the set is empty, return -1.
39        return (it == numberToIndicesMap.end() || it->second.empty()) ? -1 : *it->second.begin();
40    }
41};
42
43/**
44 * The NumberContainers object will be instantiated and called like this:
45 * NumberContainers* obj = new NumberContainers();
46 * obj->change(index, number);
47 * int param_2 = obj->find(number);
48 */
49

Typescript Solution

1// Mapping from index to number.
2const indexToNumberMap: Map<number, number> = new Map();
3
4// Mapping from number to a set of indices containing that number.
5const numberToIndicesMap: Map<number, Set<number>> = new Map();
6
7/**
8 * Changes the number at the given index.
9 * @param index The index of the number to change.
10 * @param number The new number to set at the index.
11 */
12function change(index: number, number: number): void {
13    // Check if the index already maps to a number.
14    if (indexToNumberMap.has(index)) {
15        // Retrieve the current number at the index.
16        const currentNumber = indexToNumberMap.get(index);
17        // Remove index from the set of the current number.
18        numberToIndicesMap.get(currentNumber)?.delete(index);
19    }
20    // Update the index to the new number.
21    indexToNumberMap.set(index, number);
22
23    // If there's no existing set for this number, create one.
24    if (!numberToIndicesMap.has(number)) {
25        numberToIndicesMap.set(number, new Set());
26    }
27    // Add the index to the set corresponding to the new number.
28    numberToIndicesMap.get(number)?.add(index);
29}
30
31/**
32 * Finds the smallest index that contains the given number.
33 * @param number The number to find the smallest index for.
34 * @returns The smallest index containing the given number, or -1 if not found.
35 */
36function find(number: number): number {
37    // Attempt to find the set of indices for the given number.
38    const indicesSet = numberToIndicesMap.get(number);
39    // If there's no set for the number or the set is empty, return -1.
40    if (!indicesSet || indicesSet.size === 0) {
41        return -1;
42    }
43    // Return the smallest index (first value) in the sorted set.
44    return Math.min(...indicesSet);
45}
46
47// Example usage:
48// change(1, 10);
49// let smallestIndex = find(10);
50// console.log(smallestIndex); // Outputs the smallest index where the number 10 is located, if present.
51
Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Time and Space Complexity

The given Python code defines a class NumberContainers that manages a mapping between indices and numbers and provides two methods: change to change the number at a given index, and find to find the smallest index with a given number.

Time complexity:

  • __init__ function: The initialization function has a constant time complexity of O(1), as it only involves the initialization of two data structures: a dictionary self.mp and a defaultdict of SortedSet self.t.

  • change function: The change method has a time complexity of O(log n) for updating the SortedSet in the case where the index already exists in self.mp, since SortedSet removes the element in O(log n) and adds the element in O(log n) time complexity. If an element is not present, adding to a SortedSet is O(log n) as well. Updating the dictionary self.mp has a time complexity of O(1).

  • find function: The find method has a time complexity of O(1) for accessing the first element of the SortedSet since SortedSet maintains the elements in sorted order, and accessing the elements by index is done in constant time.

Space complexity:

  • __init__ function: The space complexity for the initialization function is O(1) as it initializes empty data structures.

  • change and find functions: The space complexity is O(m + k) where m is the number of unique indices and k is the total number of unique numbers present in the NumberContainers object. This is because self.mp can potentially hold a mapping for each unique index and self.t holds unique numbers each associated with a SortedSet which in turn contains indices.

Overall, this data structure is optimized for quick updates and lookups, with the SortedSet providing efficient ordering for the indices.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫