Contains Duplicate

Problem

Data pipelines often need to validate that an incoming batch of records contains no repeated IDs before inserting them into a database. Return true if any value appears at least twice in the array; return false if every element is distinct.

Example 1:

Input: nums = [6, 4, 9, 6]
Output: true
Explanation: 6 appears twice.

Example 2:

Input: nums = [6, 4, 9, 2]
Output: false
Explanation: all elements are distinct.

Example 3:

Input: nums = [7, 7, 7, 2, 2, 5]
Output: true

Example 4:

Input: nums = []
Output: false
Explanation: an empty array has no repeated values.

Constraints:

• 0 <= nums.length <= 10^4
• -100 <= nums[i] <= 100

Solution Breakdown

Approach: seen-before set (the minimal hash map pattern).

Keep a seen set that holds every value encountered so far. Walk the array once. For each num, first ask whether it is already in seen: if it is, this is the second time the value appears, so return True immediately. Otherwise add num to the set and move on. If the loop finishes without a hit, every element was distinct, so return False. The set gives O(1) average membership tests, which is what replaces the O(n) inner scan a brute force would do for each element.

The order - check, then add - is what makes the answer correct. The loop invariant is that when you test num, seen contains exactly the elements at strictly earlier indices. So a hit means num matched something that came before it, never itself. Trace [6, 4, 9, 6]: seen grows to {6}, {6,4}, {6,4,9}, then the second 6 is found in seen and the function returns True on the fourth element without scanning further. The early return matters - on a long array with an early duplicate you stop the moment you have proof.

Edge cases: an empty array and a single-element array never enter the duplicate branch and correctly return False; repeated runs of the same value ([7,7,7,...]) are caught on the second occurrence.

Complexity: O(n) time, O(n) space - one pass with O(1) average add/lookup; the set holds up to n distinct elements in the worst case.