{x}
blog image

Design a Number Container System

Design a number container system that can do the following:

  • Insert or Replace a number at the given index in the system.
  • Return the smallest index for the given number in the system.

Implement the NumberContainers class:

  • NumberContainers() Initializes the number container system.
  • void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
  • int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.

 

Example 1:

Input
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output
[null, -1, null, null, null, null, 1, null, 2]

Explanation
NumberContainers nc = new NumberContainers();
nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.
nc.change(2, 10); // Your container at index 2 will be filled with number 10.
nc.change(1, 10); // Your container at index 1 will be filled with number 10.
nc.change(3, 10); // Your container at index 3 will be filled with number 10.
nc.change(5, 10); // Your container at index 5 will be filled with number 10.
nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.
nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20. 
nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.

 

Constraints:

  • 1 <= index, number <= 109
  • At most 105 calls will be made in total to change and find.

Solution Explanation: Design a Number Container System

This problem requires designing a data structure that efficiently handles insertion/replacement and searching for the smallest index of a given number. A combination of hash tables and ordered sets (or equivalent structures) provides an optimal solution.

Approach:

We use two data structures:

  1. index_map (Hash Table): This maps an index to the number stored at that index. This allows O(1) lookup of the number at a given index.

  2. number_map (Hash Table with Ordered Sets): This maps a number to a set of indices where that number is stored. The crucial part is that we use an ordered set (like SortedSet in Python or TreeSet in Java). This allows us to efficiently find the smallest index for a given number in O(1) time.

Algorithms:

  • change(index, number):

    1. Check if index exists in index_map. If it does, remove the old number from its corresponding set in number_map.
    2. Update index_map with the new number.
    3. Add the index to the set associated with the number in number_map.

  • find(number):

    1. Check if number exists as a key in number_map.
    2. If it exists, return the smallest index (the first element) from the ordered set. Otherwise, return -1.

Time Complexity:

  • change(index, number): O(log n), where n is the number of indices associated with the old number (due to the set operations). In the worst case, this could be O(n), but it's amortized O(log n).
  • find(number): O(1). Accessing and retrieving the first element from an ordered set is constant time.

Space Complexity: O(m + n), where m is the number of unique numbers and n is the total number of index-number pairs.

Code Implementation:

Python:

from collections import defaultdict
from sortedcontainers import SortedSet
 
class NumberContainers:
    def __init__(self):
        self.index_map = {}  # index -> number
        self.number_map = defaultdict(SortedSet)  # number -> SortedSet(indices)
 
    def change(self, index: int, number: int) -> None:
        if index in self.index_map:
            old_number = self.index_map[index]
            self.number_map[old_number].remove(index)
        self.index_map[index] = number
        self.number_map[number].add(index)
 
    def find(self, number: int) -> int:
        if number in self.number_map and self.number_map[number]:
            return self.number_map[number][0] #get the smallest index
        return -1

Java:

import java.util.*;
 
class NumberContainers {
    private Map<Integer, Integer> indexMap;
    private Map<Integer, TreeSet<Integer>> numberMap;
 
    public NumberContainers() {
        indexMap = new HashMap<>();
        numberMap = new HashMap<>();
    }
 
    public void change(int index, int number) {
        if (indexMap.containsKey(index)) {
            int oldNumber = indexMap.get(index);
            numberMap.get(oldNumber).remove(index);
        }
        indexMap.put(index, number);
        numberMap.computeIfAbsent(number, k -> new TreeSet<>()).add(index);
    }
 
    public int find(int number) {
        TreeSet<Integer> indices = numberMap.get(number);
        return indices == null || indices.isEmpty() ? -1 : indices.first();
    }
}

C++:

#include <iostream>
#include <unordered_map>
#include <set>
 
class NumberContainers {
public:
    NumberContainers() {}
 
    void change(int index, int number) {
        if (indexMap.count(index)) {
            int oldNumber = indexMap[index];
            numberMap[oldNumber].erase(index);
        }
        indexMap[index] = number;
        numberMap[number].insert(index);
    }
 
    int find(int number) {
        if (numberMap.count(number) && !numberMap[number].empty()) {
            return *numberMap[number].begin();
        }
        return -1;
    }
 
private:
    std::unordered_map<int, int> indexMap;
    std::unordered_map<int, std::set<int>> numberMap;
};

Other Languages (Go, TypeScript): The core logic remains the same; you would adapt the choice of ordered set data structures appropriately for your chosen language. For example, Go might use a redblacktree library, while TypeScript might need to implement its own or use a library like typescript-collections. The implementation detail of the ordered set will change, but the overall algorithm stays consistent.