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.

Input: [1, 2, 3, 1]         → true   (1 appears twice)
Input: [1, 2, 3, 4]         → false  (all distinct)
Input: [1, 1, 1, 3, 3, 4]   → true
Input: []                    → false

Solution

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 [1, 2, 3, 1]: seen grows to {1}, {1,2}, {1,2,3}, then the second 1 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 ([1,1,1,...]) 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.