Overview

Medium

Count, dedupe and look up in O(1)

Problem

Hashing overview: use maps and sets to count, deduplicate, and check membership in O(1) average, turning many O(n^2) scans into O(n).

In simple words

A memory that instantly recalls what you've seen turns slow searches into instant lookups.

The idea

A hash map trades memory for time: it turns 'have I seen this?' and 'how many times?' from a scan of the array into a single lookup. Almost every array problem that looks like it needs a nested loop is really asking you to remember what you have already seen.

The trick

Map for counts, set for membership — pick the smaller one that answers your question.
When values are small and bounded, a plain array of counts beats a hash map outright.
Hash lookups are O(1) on average, not worst case; adversarial keys can degrade them.

←→stepspaceplay

set{}

1/6

Optimal

timeO(n)spaceO(n)

One pass with a set.

1// a set remembers everything seen2const seen = new Set();3for (const x of nums) {4  if (seen.has(x))5    return true;6  seen.add(x);7}8return false;

Input

array: [1, 2, 3, 1]

Memory

i: —
set: {}

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:: has duplicate in [1,2,3,1]
Output:: true

Finished the walkthrough? Add it to your streak.