• 0 <= key, value <= 10⁶
• At most 10⁴ calls will be made to put, get, and remove

The task is to build the thing you have been using on earlier problems — the hash map (Two Sum leaned on one) — this time from scratch, with no built-in help. A hash map stores key → value pairs and answers three requests: put(key, value) records or overwrites a pair, get(key) returns the stored value or -1 if the key was never put, and remove(key) deletes the pair. The whole point of the structure is that all three should feel instant no matter how much it holds. Building it teaches you exactly why that lookup is fast — the magic you took on faith before.

Store every pair in one long list and search it linearly:

storage = []          # list of [key, value] pairs
def get(key):
    for k, v in storage:
        if k == key:
            return v
    return -1          # scanned everything, never found it

This is correct, and for get and remove it is also slow: to find one key you may compare against every pair, so with a million entries a single lookup can cost a million comparisons — O(N). Look closely at why it's slow: the list gives us no hint about where a key lives, so we have no choice but to check them all. The key is a perfectly good piece of information sitting right in our hand — and we're ignoring it as an address.

What if the key could tell us where its value lives directly, with no searching? Keep an array of size slots. Given a key, run it through a tiny, fixed calculation — a hash function — that converts the key into a slot number in range. The simplest one for integer keys is the remainder: index = key % size. The same key always produces the same index, so put and get compute the identical slot and meet there. No scan — we compute the location. That is the entire trick behind constant-time lookup: replace searching for a key with calculating where it must be.

There are far more possible keys than slots, so two different keys will sometimes hash to the same slot — key 1 and key 1001 both give index 1 when size is 1000. This is a collision, and it is unavoidable, so the design must absorb it rather than break on it. The fix: don't store a single pair per slot — store a small bucket (a little list) at each slot. Every key that hashes there shares the bucket. Now put computes the slot, then scans just that one short bucket to either overwrite a matching key or append a new pair; get and remove do the same short scan.

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]   # one small list per slot

    def put(self, key, value):
        idx = key % self.size
        bucket = self.buckets[idx]
        for pair in bucket:            # scan only THIS bucket, not everything
            if pair[0] == key:
                pair[1] = value        # key already here → overwrite
                return
        bucket.append([key, value])    # key is new → append

    def get(self, key):
        for pair in self.buckets[key % self.size]:
            if pair[0] == key:
                return pair[1]
        return -1

Hashing spreads N keys across size slots, so each bucket holds only about N / size pairs on average — a small constant when size is chosen sensibly — and every operation is one instant hash plus one tiny scan: O(1) average. The worst case, if a bad hash function funnels every key into one bucket, degrades back to the O(N) list we started from — which is why real hash maps invest in hash functions that scatter keys evenly and grow size as they fill. Train the reflex: any time you need to look something up by an identity you already hold — a key, an id, a name — and want it instant, a hash map converts that identity straight into a location. That is the engine underneath nearly every "have I seen this?" and "fetch by id" problem, including the array-plus-map combo you'll build next in Insert Delete GetRandom.