Contains Duplicate - Mutation Outcome - Trace Execution

Choose the mutation that would break correctness.

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

Which hypothetical mutation is most dangerous for "Contains Duplicate"?
Write down the current value before applying the next branch or update.
Mutation puzzles test invariant sensitivity. The fragile part is the ordering of state updates and checks in the hash lookup approach.

Asked at 12 companies

AdobeAirbnbAmazon

Contains Duplicate — HashSet

hashmap

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

unordered_map & unordered_set in C++ref

C++ unordered_map and unordered_set use hash tables for O(1) average operations. Include <unordered_map> and <unordered_set>. For sorted order, use map/set (O(log n) red-black tree).

-unordered_map<K,V> — O(1) insert/find/erase

-unordered_set<T> — O(1) insert/count/erase

-operator[] auto-inserts default if missing

-count(key) returns 0 or 1 (use as boolean)

#include <unordered_map>
#include <unordered_set>

unordered_map<string, int> m;
m["a"] = 1;
m.count("a");  // 1 (exists)

unordered_set<int> s = {1, 2, 3};
s.count(2);    // 1

Official docs →

unordered_map & unordered_set in C++ref

C++ unordered_map and unordered_set use hash tables for O(1) average operations. Include <unordered_map> and <unordered_set>. For sorted order, use map/set (O(log n) red-black tree).

-unordered_map<K,V> — O(1) insert/find/erase

-unordered_set<T> — O(1) insert/count/erase

-operator[] auto-inserts default if missing

-count(key) returns 0 or 1 (use as boolean)

#include <unordered_map>
#include <unordered_set>

unordered_map<string, int> m;
m["a"] = 1;
m.count("a");  // 1 (exists)

unordered_set<int> s = {1, 2, 3};
s.count(2);    // 1

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

Which hypothetical mutation is most dangerous for "Contains Duplicate"?

Before decision

Initialize an empty hash set

Critical update

Iterative single pass

Invariant check

Use a set to track seen elements for O(1) lookups