Number containers

The system assigns numbers to indices, replaces previous assignments, and asks for the smallest index currently holding a requested number.

Ownership model

• index → number hash map owns the current assignment.
• number → ordered indices owns smallest-index queries.

The ordered collection may be a balanced tree. When the language lacks one, a min-heap with lazy deletion can work.

Eager balanced-tree update

change(index, number):
    if index already has old_number:
        erase index from indices[old_number]     # remove stale ownership
        erase empty old_number collection

    assignment[index] = number
    insert index into indices[number]

find(number):
    return smallest element of indices[number], or -1

Invariant: index appears in exactly the ordered collection named by assignment[index].

flowchart LR
  accTitle: Number containers update forward and reverse ownership together
  accDescr: Changing index one from number ten to number twenty removes one from the ordered set for ten, updates the forward assignment, and inserts one into the ordered set for twenty.
  A["Before<br/>assignment 1 → 10<br/>10 → {1,4}"] --> B["change(1, 20)"]
  B --> C["One synchronized update<br/>remove from set 10<br/>assign 1 → 20<br/>insert into set 20"]
  C --> D["After<br/>10 → {4}<br/>20 → {1}"]
  D --> E["find(10) = 4<br/>find(20) = 1"]

Treat reassignment as one logical transaction: remove the old reverse fact, replace the forward fact, then create the new reverse fact.

Lazy-heap alternative

Push every new (index) into the heap for its number. During find(number), pop while assignment[heap_top] != number. This simplifies updates but stores stale entries and makes cleanup query-driven.

Complexity and traps

• Balanced-tree change: O(log n); find minimum: O(1) or O(log n) by API.
• Lazy heap: O(log n) push and amortized cleanup.
• Reassigning an index to the same number must not corrupt membership.
• Eager deletion must remove empty per-number containers.
• Lazy deletion must verify the current assignment before returning a heap top.

Practice

LeetCode: Number Containers System

Tested templates

PythonC++17C++11

class NumberContainers:
    """Map indices to numbers and numbers to lazy min-heaps of indices."""

    def __init__(self) -> None:
        self.index_value: dict[int, int] = {}
        self.value_indices: dict[int, list[int]] = {}

    def change(self, index: int, value: int) -> None:
        if index < 0:
            raise ValueError("index must be nonnegative")
        self.index_value[index] = value
        # Old heap entries remain; find removes them only when exposed.
        heappush(self.value_indices.setdefault(value, []), index)

    def find(self, value: int) -> int:
        candidates = self.value_indices.get(value, [])
        while candidates and self.index_value.get(candidates[0]) != value:
            heappop(candidates)
        return candidates[0] if candidates else -1

class NumberContainers {
 public:
  void change(int index, int value) {
    if (index < 0) {
      throw std::invalid_argument("index must be nonnegative");
    }
    const auto existing = index_value_.find(index);
    if (existing != index_value_.end()) {
      value_indices_[existing->second].erase(index);
    }
    index_value_[index] = value;
    value_indices_[value].insert(index);
  }

  int find(int value) const {
    const auto found = value_indices_.find(value);
    return found == value_indices_.end() || found->second.empty()
               ? -1
               : *found->second.begin();
  }

 private:
  std::unordered_map<int, int> index_value_;
  std::unordered_map<int, std::set<int>> value_indices_;
};

class NumberContainers {
 public:
  void change(int index, int value) {
    if (index < 0) {
      throw std::invalid_argument("index must be nonnegative");
    }
    const auto existing = index_value_.find(index);
    if (existing != index_value_.end()) {
      value_indices_[existing->second].erase(index);
    }
    index_value_[index] = value;
    value_indices_[value].insert(index);
  }

  int find(int value) const {
    const auto found = value_indices_.find(value);
    return found == value_indices_.end() || found->second.empty()
               ? -1
               : *found->second.begin();
  }

 private:
  std::unordered_map<int, int> index_value_;
  std::unordered_map<int, std::set<int>> value_indices_;
};

Python demonstrates lazy heap cleanup; C++ demonstrates eager std::set removal. Both preserve the same smallest-index contract.