# Design a Number Container System
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-a-number-container-system)
Canonical: https://scaleengineer.com/dsa/problems/design-a-number-container-system
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table, Heap (Priority Queue), Ordered Set
---
## Problem
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`.

# Approaches
## Brute Force with a Single HashMap
This approach uses a single hash map to store the mapping from an index to the number it contains. The `change` operation is efficient, simply involving an update to the map. However, the `find` operation is slow. To find the smallest index for a given number, we must iterate through all the entries in the hash map, checking each one to see if its value matches the target number, and keeping track of the minimum index found.
**Time:** - **`change(index, number)`**: O(1) on average.
- **`find(number)`**: O(N), where N is the number of unique indices stored in the system. In the worst case, we must scan all N entries. · **Space:** O(N), where N is the number of unique indices for which `change` has been called. The hash map stores one entry for each unique index.
**Pros:** Simple to understand and implement.; The `change` operation is very fast, taking O(1) average time.; Uses less complex data structures.
**Cons:** The `find` operation is very slow, with a time complexity of O(N), where N is the number of entries in the map. This will likely result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
This approach uses a single `HashMap<Integer, Integer>` called `indexToNumberMap` to store the container system's state. The key represents the `index`, and the value represents the `number` at that index.

### `change(index, number)`
The `change` method is straightforward. It simply inserts or updates the entry for the given `index` with the new `number` using `indexToNumberMap.put(index, number)`. This is an efficient O(1) average time operation.

### `find(number)`
The `find` method is less efficient. It must search for the smallest index associated with a given `number`. This is done by iterating through the entire `indexToNumberMap`. A variable, `minIndex`, is used to keep track of the smallest index found so far that contains the target `number`. For each entry in the map, if the value matches the target `number`, its key (the index) is compared with `minIndex`, and `minIndex` is updated if a smaller index is found. If no matching number is found after checking all entries, the initial value of -1 is returned.

```java
import java.util.HashMap;
import java.util.Map;

class NumberContainers {
    private Map<Integer, Integer> indexToNumberMap;

    public NumberContainers() {
        indexToNumberMap = new HashMap<>();
    }

    public void change(int index, int number) {
        indexToNumberMap.put(index, number);
    }

    public int find(int number) {
        int minIndex = -1;
        for (Map.Entry<Integer, Integer> entry : indexToNumberMap.entrySet()) {
            if (entry.getValue() == number) {
                if (minIndex == -1 || entry.getKey() < minIndex) {
                    minIndex = entry.getKey();
                }
            }
        }
        return minIndex;
    }
}
```
### Algorithm
- **Data Structure**: Use a single `HashMap<Integer, Integer>` to store the mapping from an `index` to a `number`.
- **`change(index, number)`**: Simply update the map with the new `index` and `number`. This is an O(1) operation on average.
- **`find(number)`**: 
  - Initialize a variable `minIndex` to track the smallest index, setting it initially to -1.
  - Iterate through every entry in the hash map.
  - If an entry's value matches the target `number`, update `minIndex` with the entry's key if it's smaller than the current `minIndex` (or if `minIndex` is still -1).
  - After iterating through the entire map, return `minIndex`.

## Optimized with Two HashMaps and TreeSet
This approach significantly improves the performance of the `find` operation by using a second data structure. In addition to the `index -> number` map, we maintain another map from a `number` to a collection of all `indices` where that number is located. To efficiently find the smallest index, this collection of indices must be kept sorted. A `TreeSet` is an ideal choice for this purpose as it allows for logarithmic time complexity for additions, removals, and retrieval of the minimum element.
**Time:** - **`change(index, number)`**: O(log K), where K is the number of indices associated with a number. In the worst case, K can be up to N (the total number of `change` calls), so the complexity is O(log N).
- **`find(number)`**: O(log K), where K is the number of indices for the given number. The `.first()` operation on a Java `TreeSet` takes logarithmic time. The worst-case complexity is O(log N). · **Space:** O(N), where N is the total number of `change` operations. In the worst case, `indexToNumber` stores N entries, and the total number of elements across all `TreeSet`s in `numberToIndices` is also N.
**Pros:** Highly efficient for both `change` and `find` operations.; Provides a good balance between the complexities of the two operations, making it suitable for a high volume of calls.
**Cons:** More complex to implement compared to the brute-force approach.; Uses more memory due to the overhead of two maps and `TreeSet` objects.
### Explanation
This optimized solution addresses the O(N) complexity of the `find` operation in the brute-force approach. It employs two main data structures to maintain the system's state efficiently.

1.  **`indexToNumber` (`HashMap<Integer, Integer>`)**: This map stores the direct relationship from an `index` to the `number` it contains. It's crucial for the `change` operation to know which number was previously at an index, so we can update our second data structure.
2.  **`numberToIndices` (`HashMap<Integer, TreeSet<Integer>>`)**: This is the core of the optimization. It maps a `number` to a `TreeSet` of all indices that contain this number. A `TreeSet` is used because it automatically keeps the indices in sorted order, which allows us to find the minimum index very quickly.

### `change(index, number)`
When `change` is called, we first check if the `index` already has a number. If it does (`indexToNumber.containsKey(index)`), we must remove the `index` from the `TreeSet` of the `oldNumber`. Then, we update the `indexToNumber` map and add the `index` to the `TreeSet` of the new `number`. These additions and removals from the `TreeSet` are efficient, taking O(log K) time, where K is the number of indices for a given number.

### `find(number)`
The `find` operation becomes highly efficient. We simply look up the `number` in our `numberToIndices` map. If an entry exists, we retrieve the `TreeSet` of indices. Since the `TreeSet` is always sorted, the smallest index is the first element, which can be accessed using the `.first()` method in O(log K) time. If no entry exists or the set is empty, we return -1.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

class NumberContainers {
    private Map<Integer, Integer> indexToNumber;
    private Map<Integer, TreeSet<Integer>> numberToIndices;

    public NumberContainers() {
        indexToNumber = new HashMap<>();
        numberToIndices = new HashMap<>();
    }

    public void change(int index, int number) {
        if (indexToNumber.containsKey(index)) {
            int oldNumber = indexToNumber.get(index);
            if (oldNumber == number) {
                return; // No change needed
            }
            TreeSet<Integer> indices = numberToIndices.get(oldNumber);
            indices.remove(index);
            if (indices.isEmpty()) {
                numberToIndices.remove(oldNumber);
            }
        }

        indexToNumber.put(index, number);
        numberToIndices.computeIfAbsent(number, k -> new TreeSet<>()).add(index);
    }

    public int find(int number) {
        TreeSet<Integer> indices = numberToIndices.get(number);
        if (indices == null || indices.isEmpty()) {
            return -1;
        }
        return indices.first();
    }
}
```
### Algorithm
- **Data Structures**: Use two maps: 
  1. `indexToNumber`: A `HashMap<Integer, Integer>` to map an index to its number.
  2. `numberToIndices`: A `HashMap<Integer, TreeSet<Integer>>` to map a number to a sorted set of its indices.
- **`change(index, number)`**:
  - Check if `index` already exists in `indexToNumber`. If so, get its `oldNumber`.
  - Remove `index` from the `TreeSet` associated with `oldNumber` in `numberToIndices`.
  - Update `indexToNumber` with the new `(index, number)` pair.
  - Add `index` to the `TreeSet` associated with the new `number` in `numberToIndices`, creating a new `TreeSet` if one doesn't exist.
- **`find(number)`**:
  - Look up the `TreeSet` of indices for the given `number` in `numberToIndices`.
  - If the set exists and is not empty, return its first (smallest) element using `.first()`.
  - Otherwise, return -1.

# Solutions
### Java

```java
class NumberContainers { private Map < Integer , Integer > mp = new HashMap <>(); private Map < Integer , TreeSet < Integer >> t = new HashMap <>(); public NumberContainers () { } public void change ( int index , int number ) { if ( mp . containsKey ( index )) { int v = mp . get ( index ); t . get ( v ). remove ( index ); if ( t . get ( v ). isEmpty ()) { t . remove ( v ); } } mp . put ( index , number ); t . computeIfAbsent ( number , k -> new TreeSet <>()). add ( index ); } public int find ( int number ) { return t . containsKey ( number ) ? t . get ( number ). first () : - 1 ; } } /** * Your NumberContainers object will be instantiated and called as such: * NumberContainers obj = new NumberContainers(); * obj.change(index,number); * int param_2 = obj.find(number); */
```

### CPP

```cpp
class NumberContainers { public: map < int , int > mp ; map < int , set < int >> t ; NumberContainers () { } void change ( int index , int number ) { auto it = mp . find ( index ); if ( it != mp . end ()) { t [ it -> second ]. erase ( index ); it -> second = number ; } else mp [ index ] = number ; t [ number ]. insert ( index ); } int find ( int number ) { auto it = t . find ( number ); return it == t . end () || it -> second . empty () ? - 1 : * it -> second . begin (); } }; /** * Your NumberContainers object will be instantiated and called as such: * NumberContainers* obj = new NumberContainers(); * obj->change(index,number); * int param_2 = obj->find(number); */
```

### Python

```python
from sortedcontainers import SortedSet class NumberContainers : def __init__ ( self ): self . mp = {} self . t = defaultdict ( SortedSet ) def change ( self , index : int , number : int ) -> None : if index in self . mp : v = self . mp [ index ] self . t [ v ]. remove ( index ) self . mp [ index ] = number self . t [ number ]. add ( index ) def find ( self , number : int ) -> int : s = self . t [ number ] return s [ 0 ] if s else - 1 # Your NumberContainers object will be instantiated and called as such: # obj = NumberContainers() # obj.change(index,number) # param_2 = obj.find(number)
```