Contains Duplicate - Trace & Predict

Trace execution and predict values

Problem Brief

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Puzzle Hints

Trace the concrete state change for Contains Duplicate.
Write down the current value before applying the next branch or update.
At i=3, 1 is already in the set, so we return true.

Asked at 12 companies

AdobeAirbnbAmazon

Contains Duplicate — HashSet

hashmap

Input: [1,2,3,1]. Use HashSet to detect duplicates

Map & Set in JavaScriptref

JavaScript provides Map for key-value pairs and Set for unique values. Both offer O(1) average lookup, insert, and delete. Unlike plain objects, Map preserves insertion order and allows any type as keys.

-new Map() — O(1) get/set/has/delete

-new Set() — O(1) add/has/delete, auto-deduplicates

-Map.get(key) returns undefined if missing

-for...of iterates Map entries as [key, value]

const map = new Map();
map.set('a', 1);    // set key-value
map.get('a');        // 1
map.has('a');        // true

const set = new Set([1, 2, 2, 3]);
set.size;            // 3 (deduped)
set.has(2);          // true

Official docs →

Map & Set in JavaScriptref

-new Map() — O(1) get/set/has/delete

-new Set() — O(1) add/has/delete, auto-deduplicates

-Map.get(key) returns undefined if missing

-for...of iterates Map entries as [key, value]

const map = new Map();
map.set('a', 1);    // set key-value
map.get('a');        // 1
map.has('a');        // true

const set = new Set([1, 2, 2, 3]);
set.size;            // 3 (deduped)
set.has(2);          // true

Official docs →

How to think: Hash Map / Setguide

You need O(1) lookups — checking if something exists, counting frequencies, or finding pairs.

1.Ask: "Am I searching for something repeatedly?" → Hash Map

2.Ask: "Do I need to check existence?" → Set

3.Ask: "Do I need to count occurrences?" → Map with value = count

4.Ask: "Do I need to find a pair that satisfies a condition?" → Store complement in Map

5.The tradeoff: O(n) extra space buys you O(1) per lookup

vs Nested loops (O(n²)): You're comparing every element against every other — a Map does it in one pass

vs Sorting (O(n log n)): You just need existence/frequency checks, not order

find pairtwo numbers thatfrequencycountduplicateanagramgroup by

How to think: Hash Map / Setguide

You need O(1) lookups — checking if something exists, counting frequencies, or finding pairs.

1.Ask: "Am I searching for something repeatedly?" → Hash Map

2.Ask: "Do I need to check existence?" → Set

3.Ask: "Do I need to count occurrences?" → Map with value = count

4.Ask: "Do I need to find a pair that satisfies a condition?" → Store complement in Map

5.The tradeoff: O(n) extra space buys you O(1) per lookup

vs Nested loops (O(n²)): You're comparing every element against every other — a Map does it in one pass

vs Sorting (O(n log n)): You just need existence/frequency checks, not order

find pairtwo numbers thatfrequencycountduplicateanagramgroup by

1nums = [1, 2, 3, 1]
2seen = Set()
3 
4i=0: add 1, seen={1}
5i=1: add 2, seen={1,2}
6i=2: add 3, seen={1,2,3}
7i=3: has(1)?

Variables

Step through to see values...

Step 4

Is 1 already in seen at i=3? (yes/no)

const map = new Map(); map.set('a', 1); // set key-value map.get('a'); // 1 map.has('a'); // true const set = new Set([1, 2, 2, 3]); set.size; // 3 (deduped) set.has(2); // true