Problem statement

A row of containers is numbered 1, 2, 3, …; each container is empty or holds one number. Write the class NumberContainers:

• NumberContainers() creates the row with every container empty.
• void change(int index, int number) puts number into container index. If that container already held a number, the old one is replaced.
• int find(int number) returns the smallest index of a container that currently holds number, or -1 if no container does.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["NumberContainers","find","change","change","change","change","find","change","find"]
[[],[7],[4,7],[2,7],[9,7],[6,7],[7],[2,3],[7]]
Output: [null,-1,null,null,null,null,2,null,4]
Explanation: No container holds 7 at first. After 7 is put into containers 4, 2, 9 and 6, the smallest is 2. Replacing container 2's number with 3 leaves 4 as the smallest holding 7.

Example 2

Input: ["NumberContainers","change","change","find","change","find","find"]
[[],[1000000000,5],[1,1000000000],[1000000000],[1,5],[5],[1000000000]]
Output: [null,null,null,1,null,1,-1]
Explanation: Indices and numbers both go up to 10^9. Container 1 first holds 10^9 and then 5, so afterwards 5 is found at index 1 (smaller than 10^9) and nothing holds 10^9 any more.

Constraints

• 1 <= index, number <= 10^9
• At most 10^5 calls are made in total to change and find

Hints for Design a Number Container System

1. Hint 1

   You need two directions: which number each index holds, and which indices hold each number.

2. Hint 2

   For each number keep its indices in a structure that gives the minimum fast — an ordered set, or a min-heap.

3. Hint 3

   When change overwrites an index, its old number loses that index. With an ordered set, remove it there; with a heap, leave it and discard heap tops that no longer hold the number when find looks (lazy deletion).

How to solve Design a Number Container System

Keep a map index → number and, for every number, an ordered set (or lazy min-heap) of the indices holding it. find is then the smallest element of one set.

Approach

1. change(index, number): if index already held some old, remove index from old's set. Store index → number and add index to number's set.
2. find(number): return the smallest index in number's set, or -1 if the set is missing or empty.
3. Lazy variant with a heap: change only pushes index onto number's heap; find pops tops whose current number (from the map) is not number until a valid one is on top.

Why it works

Each set holds exactly the indices whose current number is its key: change moves the index out of its old set and into its new one, and nothing else changes which number an index holds. The smallest element of the set is therefore the answer. In the lazy version a stale heap entry is never returned, because find checks it against the map before trusting it.

Complexity

• Time — O(log n) per call (amortised for the lazy heap)
• Space — O(n) for n changes

Pitfalls

• Forgetting to remove the index from its previous number's set makes find report a container that has since been overwritten.
• Writing the same number into the same container twice must leave it findable — with a set that is automatic; with a lazy heap, duplicates are harmless.

Reference solution

Python

import heapq

class NumberContainers:

    def __init__(self):
        self.at = {}     # index -> number it holds now
        self.heaps = {}  # number -> min-heap of indices (may hold stale ones)

    def change(self, index: int, number: int) -> None:
        self.at[index] = number
        heapq.heappush(self.heaps.setdefault(number, []), index)

    def find(self, number: int) -> int:
        h = self.heaps.get(number)
        while h and self.at[h[0]] != number:
            heapq.heappop(h)  # that container was overwritten since
        return h[0] if h else -1

Java

class NumberContainers {
    private HashMap<Integer, Integer> at = new HashMap<>();           // index -> number
    private HashMap<Integer, TreeSet<Integer>> idx = new HashMap<>(); // number -> indices

    public NumberContainers() {
    }

    public void change(int index, int number) {
        Integer old = at.put(index, number);
        if (old != null) idx.get(old).remove(index);
        idx.computeIfAbsent(number, k -> new TreeSet<>()).add(index);
    }

    public int find(int number) {
        TreeSet<Integer> s = idx.get(number);
        return s == null || s.isEmpty() ? -1 : s.first();
    }
}

C++

class NumberContainers {
    unordered_map<int, int> at;       // index -> number
    unordered_map<int, set<int>> idx; // number -> indices
public:
    NumberContainers() {}

    void change(int index, int number) {
        auto it = at.find(index);
        if (it != at.end()) idx[it->second].erase(index);
        at[index] = number;
        idx[number].insert(index);
    }

    int find(int number) {
        auto it = idx.find(number);
        if (it == idx.end() || it->second.empty()) return -1;
        return *it->second.begin();
    }
};

JavaScript

var NumberContainers = function() {
    this.at = new Map();  // index -> number it holds now
    this.idx = new Map(); // number -> its indices, sorted ascending
};

function ncLowerBound(a, x) {
    var lo = 0, hi = a.length;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (a[mid] < x) lo = mid + 1; else hi = mid;
    }
    return lo;
}

NumberContainers.prototype.change = function(index, number) {
    if (this.at.has(index)) {
        var old = this.idx.get(this.at.get(index));
        old.splice(ncLowerBound(old, index), 1);
    }
    this.at.set(index, number);
    if (!this.idx.has(number)) this.idx.set(number, []);
    var a = this.idx.get(number);
    a.splice(ncLowerBound(a, index), 0, index);
};

NumberContainers.prototype.find = function(number) {
    var a = this.idx.get(number);
    return a && a.length > 0 ? a[0] : -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium