Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Overview

Trade space for O(1) lookups — sets & maps
step 1 / 12
3
8
2
5
[0][1][2][3]
The hashing idea
▸
1// a hash table = O(1) average insert + lookup
2set ← {}        // membership: "have I seen x?"
3for x in arr: set.add(x)
4query: x in set        // O(1), no re-scan
5map ← {}        // payload: value → index / count
6for i, x in arr: map[x] = i
7// average O(1); collisions are the worst case
state
  • insertO(1) avg
  • lookupO(1) avg
  • costextra space

line 1A HASH TABLE answers one question almost instantly: "have I seen this before?" — and, if you want, "where / how many?". It stores keys in buckets chosen by a hash of the key, so insert and lookup are O(1) on AVERAGE. You trade extra MEMORY for speed.