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.

Examples

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 <= 10^9
  • At most 10^5 calls will be made in total to change and find.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Using Hashmap + Priority Queue ❌

  1. Data Structures:
    • Use a dictionary to map indices to their corresponding numbers.
    • Use another dictionary to map numbers to a min-heap (priority queue) that keeps track of all indices for that number. This helps in maintaining the smallest index efficiently.
  2. Operations:
    • For the change operation, update the index-to-number mapping and add the index to the number’s heap.
    • For the find operation, simply fetch the smallest index from the heap of the required number.

Code

Java
class NumberContainers {

    private Map<Integer, Integer> indexToNumber;
    private Map<Integer, PriorityQueue<Integer>> numberToIndices;

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

    public void change(int index, int number) {
        if (indexToNumber.containsKey(index)) {
            int oldNum = indexToNumber.get(index);
            if (numberToIndices.containsKey(oldNum)) {
                numberToIndices.get(oldNum).remove(index);
                if (numberToIndices.get(oldNum).isEmpty()) {
                    numberToIndices.remove(oldNum);
                }
            }
        }
        indexToNumber.put(index, number);
        numberToIndices.putIfAbsent(number, new PriorityQueue<>());
        numberToIndices.get(number).offer(index);
    }

    public int find(int number) {
        if (!numberToIndices.containsKey(number) 
	        || numberToIndices.get(number).isEmpty()) {
            return -1;
        }
        return numberToIndices.get(number).peek();
    }
}
Python
class NumberContainers:
    
    def __init__(self) -> None:
        self.index_to_number: Dict[int, int] = {}
        self.number_to_indices: Dict[int, List[int]] = {}

    def change(self, index: int, number: int) -> None:
        if index in self.index_to_number:
            old_num = self.index_to_number[index]
            if old_num in self.number_to_indices:
                self.number_to_indices[old_num].remove(index)
                if not self.number_to_indices[old_num]:
                    del self.number_to_indices[old_num]
        self.index_to_number[index] = number
        if number not in self.number_to_indices:
            self.number_to_indices[number] = []
        heappush(self.number_to_indices[number], index)

    def find(self, number: int) -> int:
        if number not in self.number_to_indices or not self.number_to_indices[number]:
            return -1
        return self.number_to_indices[number][0]

Complexity

  • ⏰ Time complexity:
    • change: O(n) for the heap operations.
    • find: O(1) to get the smallest element from the heap.
  • 🧺 Space complexity: O(N) where N is the number of indices due to the storage in the dictionaries.

Method 2 - Using Map + Priority Queue + Set

In the previous solution, removing an index from heap will take O(n) time, resulting in TLE. For that, we can implement lazy deletion in find instead. We can use set to track the valid indices.

Code

Java
class NumberContainers {
    private Map<Integer, Integer> indexToNumber;
    private Map<Integer, PriorityQueue<Integer>> numberToIndices;
    private Map<Integer, Set<Integer>> validIndices;

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

    public void change(int index, int number) {
        if (indexToNumber.containsKey(index)) {
            int oldNum = indexToNumber.get(index);
            if (numberToIndices.containsKey(oldNum)) {
                validIndices.get(oldNum).remove(index);
                // Lazy deletion, don't remove from the heap here
            }
        }

        indexToNumber.put(index, number);
        numberToIndices.putIfAbsent(number, new PriorityQueue<>());
        validIndices.putIfAbsent(number, new HashSet<>());

        numberToIndices.get(number).offer(index);
        validIndices.get(number).add(index);
    }

    public int find(int number) {
        if (!numberToIndices.containsKey(number)) {
            return -1;
        }

        PriorityQueue<Integer> indicesHeap = numberToIndices.get(number);
        Set<Integer> validSet = validIndices.get(number);

        while (!indicesHeap.isEmpty() && !validSet.contains(indicesHeap.peek())) {
            indicesHeap.poll();  // Remove invalid indices from the heap
        }

        return indicesHeap.isEmpty() ? -1 : indicesHeap.peek();
    }
}
Python
class NumberContainers:

    def __init__(self) -> None:
        self.index_to_number: Dict[int, int] = {}
        self.number_to_indices: Dict[int, List[int]] = {}
        self.valid_indices: Dict[int, Set[int]] = {}

    def change(self, index: int, number: int) -> None:
        if index in self.index_to_number:
            old_num = self.index_to_number[index]
            if old_num in self.number_to_indices:
                self.valid_indices[old_num].discard(index)
                # Lazy deletion, don't remove from the heap here

        self.index_to_number[index] = number
        if number not in self.number_to_indices:
            self.number_to_indices[number] = []
            self.valid_indices[number] = set()

        heappush(self.number_to_indices[number], index)
        self.valid_indices[number].add(index)

    def find(self, number: int) -> int:
        if number not in self.number_to_indices:
            return -1

        heap = self.number_to_indices[number]
        valid = self.valid_indices[number]

        while heap and heap[0] not in valid:
            heappop(heap)  # Remove invalid indices from the heap

        return heap[0] if heap else -1

Complexity

  • ⏰ Time complexity
    • change: O(log n) for insertion into the heap.
    • find: due to potentially discarding invalid entries at the top of the heap.
  • 🧺 Space complexity: O(n)

Method 3 - Using Map + TreeSet

Removing an element by value from a heap is not efficient and can degrade the performance. To fix this, we can add a set to track the valid indices. This way, when we retrieve values from the heap, we can skip the invalid entries.

  1. Data Structures:
    • Use a dictionary to map indices to their corresponding numbers.
    • Use another dictionary to map numbers to a min-heap that keeps track of all indices for that number.
    • Use a set to track active (valid) indices for each number. When an index is replaced, it is removed from the set.
  2. Operations:
    • For the change operation, update the index-to-number mapping and add the index to the number’s heap.
    • For the find operation, skip over invalid indices to return the smallest valid index.

Code

Java
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 oldNum = indexToNumber.get(index);
            numberToIndices.get(oldNum).remove(index);
            if (numberToIndices.get(oldNum).isEmpty()) {
                numberToIndices.remove(oldNum);
            }
        }
        indexToNumber.put(index, number);
        numberToIndices.putIfAbsent(number, new TreeSet<>());
        numberToIndices.get(number).add(index);
    }

    public int find(int number) {
        if (!numberToIndices.containsKey(number) || numberToIndices.get(number).isEmpty()) {
            return -1;
        }
        return numberToIndices.get(number).first();
    }
}
Python
class NumberContainers:

    def __init__(self) -> None:
        self.index_to_number: Dict[int, int] = {}
        self.number_to_indices: Dict[int, SortedSet] = {}

    def change(self, index: int, number: int) -> None:
        if index in self.index_to_number:
            old_num = self.index_to_number[index]
            self.number_to_indices[old_num].discard(index)
            if not self.number_to_indices[old_num]:
                del self.number_to_indices[old_num]
        self.index_to_number[index] = number
        if number not in self.number_to_indices:
            self.number_to_indices[number] = SortedSet()
        self.number_to_indices[number].add(index)

    def find(self, number: int) -> int:
        if number not in self.number_to_indices or not self.number_to_indices[number]:
            return -1
        return self.number_to_indices[number][0]

Complexity

  • ⏰ Time complexity
    • O(log n) due to insertion and deletion in a balanced tree structure (TreeSet / SortedSet).
    • O(1) to get the smallest element from the set.
  • 🧺 Space complexity: O(n) for storing n entries in the index-to-number and number-to-indices maps.