Design a Number Container System

medium heap hash map design

Problem

Build a NumberContainers class with two operations. change(index, number) stores number in the container at index, replacing whatever number was there before. find(number) returns the smallest index whose container currently holds number, or −1 if no container does.

Indices and numbers can be as large as 10⁹ and many containers may hold the same number, so scanning every container on each query is far too slow.

Inputfind(10); change(2,10); change(1,10); change(3,10); change(5,10); find(10); change(1,20); find(10)

Output-1, 1, 2

The first find sees no 10s; after four changes the smallest index holding 10 is 1; once index 1 is rewritten to 20, the answer shifts to 2.

operations (find(n) or change(i,n), separated by ';')

import heapq

class NumberContainers:
    def __init__(self):
        self.num_at = {}     # index -> number
        self.heaps = {}      # number -> min-heap of indices

    def change(self, index, number):
        self.num_at[index] = number
        if number not in self.heaps:
            self.heaps[number] = []
        heapq.heappush(self.heaps[number], index)

    def find(self, number):
        heap = self.heaps.get(number, [])
        while heap and self.num_at[heap[0]] != number:
            heapq.heappop(heap)          # discard stale index
        return heap[0] if heap else -1

class NumberContainers {
  constructor() {
    this.numAt = new Map();   // index -> number
    this.heaps = new Map();   // number -> min-heap of indices
  }
  change(index, number) {
    this.numAt.set(index, number);
    if (!this.heaps.has(number)) this.heaps.set(number, []);
    heapPush(this.heaps.get(number), index);
  }
  find(number) {
    const heap = this.heaps.get(number) || [];
    while (heap.length && this.numAt.get(heap[0]) !== number) {
      heapPop(heap);                     // discard stale index
    }
    return heap.length ? heap[0] : -1;
  }
}
// heapPush / heapPop maintain a binary min-heap of indices.

class NumberContainers {
    Map<Integer, Integer> numAt = new HashMap<>();
    Map<Integer, PriorityQueue<Integer>> heaps = new HashMap<>();

    public void change(int index, int number) {
        numAt.put(index, number);
        heaps.computeIfAbsent(number, k -> new PriorityQueue<>())
             .offer(index);
    }

    public int find(int number) {
        PriorityQueue<Integer> heap = heaps.get(number);
        if (heap == null) return -1;
        while (!heap.isEmpty() && numAt.get(heap.peek()) != number) {
            heap.poll();                 // discard stale index
        }
        return heap.isEmpty() ? -1 : heap.peek();
    }
}

class NumberContainers {
    unordered_map<int, int> numAt;   // index -> number
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> heaps;
public:
    void change(int index, int number) {
        numAt[index] = number;
        heaps[number].push(index);
    }

    int find(int number) {
        auto it = heaps.find(number);
        if (it == heaps.end()) return -1;
        auto& heap = it->second;
        while (!heap.empty() && numAt[heap.top()] != number) {
            heap.pop();                  // discard stale index
        }
        return heap.empty() ? -1 : heap.top();
    }
};

Explanation

find(number) wants the smallest index holding a number, which screams min-heap — but change can silently overwrite an index, and deleting an arbitrary element from a heap is awkward. The key insight is lazy deletion: keep the ground truth in a hash map and let the heaps hold stale leftovers, cleaning them up only when a query actually looks at them.

We keep two structures: num_at, a map from index to the number it currently holds, and heaps, a map from each number to a min-heap of indices where that number was ever placed. change(index, number) writes the map and pushes index onto number's heap — it never visits the heap of the number being overwritten, so an outdated copy of the index simply stays behind there.

find(number) peeks at the top of number's heap. If the map says that index no longer holds number, the entry is stale, so we pop it and peek again. The first top that agrees with the map is the smallest valid index; if the heap runs dry (or never existed), we return −1. Popping stale entries permanently removes them, so no query pays for the same garbage twice.

On the default example, the first find(10) sees no heap for 10 and returns −1. Four changes fill indices 2, 1, 3, 5 with 10, so 10's heap is [1, 2, 3, 5] and find(10) returns 1. Then change(1, 20) rewrites index 1; the 1 inside 10's heap is now stale. The last find(10) pops that stale 1 and returns 2, the smallest index that still holds 10.

Each change does one map write and one heap push, O(log n). Each heap entry is pushed once and popped at most once over the structure's whole lifetime, so all the stale-popping across every find amortizes against the pushes that created the entries — O(log n) amortized per operation, with O(n) space for one map entry plus one heap entry per change.

Time: O(log n) amortized per op Space: O(n)