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.
Examples
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Constraints
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
Prerequisites
Hash sets and hash maps — expected O(1) membership and lookup, and what "expected" costs when hashes collide. Array traversal, and the habit of asking what a second pass buys over a nested loop.
How to think about it
1. Brute Force
Intuition
Compare every pair and answer as soon as two match. It is the definition of the problem read literally, and it is worth stating out loud before improving on it — an interviewer wants to see that you know what you are beating.
Algorithm
1. For each index i, walk every index j after it. 2. If nums[i] equals nums[j], the array has a duplicate — return true. 3. If the loops finish without a match, every value was distinct — return false.
Time & Space
Time O(n^2) — every pair is examined. Space O(1); nothing is stored.
2. Hash Set Optimal
Intuition
The nested loop re-asks one question: have I seen this value already? A set answers it in constant time, which collapses the pairs into a single pass. Trading memory for time is the whole move, and naming that trade is the answer an interviewer is listening for.
Algorithm
1. Keep a set of the values seen so far. 2. For each value, if it is already in the set, return true. 3. Otherwise add it and continue; reaching the end means no duplicates.
Time & Space
Time O(n) — one pass, expected O(1) per lookup. Space O(n) for the set, which is the price of the speed.