Contains Duplicate

Learning goal: Recognize when an array problem is asking whether any value has appeared before.

Core idea We do not need to count every value before deciding whether a duplicate exists. We only need to remember which values have already been encountered. A set is designed for exactly this membership question: "Have I seen this value before?"

Algorithm plan

• Start with an empty set named seen.
• Scan the array from left to right.
• If the current value is already in seen, return true.
• Otherwise, insert it and continue.
• If the scan finishes, return false.

Micro-example For [4, 1, 7, 4], insert 4, 1, and 7. The final 4 is already in seen, so the answer is true immediately.

Pitfalls

• Do not compare every pair with nested loops unless the constraints are tiny.
• Check membership before inserting, so the repeated occurrence is visible.
• The set stores values, not their original indices.

Recap

• The goal is duplicate detection, not frequency reporting.
• A set stores exactly the history needed for the decision.
• Stop at the first repeated value.

Learning goal: Understand why a hash set turns duplicate detection into a linear scan.

Core idea A hash set organizes values so that checking membership and adding a new value take O(1) time on average. That means the algorithm can process each array element once instead of repeatedly searching the part of the array that came before it. The set contains no duplicates by definition, which makes it a natural summary of the prefix scanned so far.

Data structure model

Micro-example After reading [4, 1, 7], seen = {4, 1, 7}. Reading another 4 produces a membership hit, so no further work is needed.

Pitfalls

• Average O(1) does not mean the set is magically free; it uses O(n) additional memory.
• A frequency map is valid, but it stores counts that this yes/no problem does not need.
• Do not confuse a set with a list membership check, which is O(n).

Recap

• Hashing makes membership checks fast on average.
• The set represents distinct values in the scanned prefix.
• Duplicate detection is a collision between the current value and seen.

Learning goal: Translate the set idea into a correct implementation and compare it with sorting.

Core idea The one-pass approach maintains the invariant that seen contains exactly the distinct values from the portion already processed. Before inserting nums[i], test membership. A hit proves that the value occurred earlier; a miss preserves the invariant after insertion.

Algorithm plan

seen = empty set
for value in nums:
    if value is in seen:
        return true
    add value to seen
return false

An equivalent formulation builds a set from the entire array and compares its size with nums.length. The explicit scan is often clearer because it can return immediately when the first duplicate appears.

Micro-example For [4, 1, 7, 4], the fourth iteration finds 4 already stored and returns immediately.

Pitfalls

• Sorting is correct but slower asymptotically.
• If preserving the input matters, sorting may require a copy.
• The nested-loop approach is the common O(n²) detour.

Recap

• Check, then insert each value.
• Early exit makes the scan especially efficient on duplicate-heavy inputs.
• Hashing is both faster and clearer here than pairwise comparison.

Learning goal: Trace the invariant through one complete example and see exactly where the algorithm returns.

Core idea Use the example [4, 1, 7, 4]. At the beginning of iteration i, seen contains every distinct value from indices before i. Each unseen value is added; the repeated final 4 violates the expectation that the current value is new, proving the answer immediately.

Algorithm plan

• Inspect the current array value.
• Check membership in seen.
• If absent, add it and advance.
• If present, return true without scanning the remaining suffix.

Micro-example

Pitfalls

• The first occurrence of 4 is not a duplicate by itself.
• Do not erase values after checking them; future checks depend on the accumulated set.
• Once a duplicate is found, continuing is unnecessary.

Recap

• The invariant holds after every insertion.
• The fourth value creates the first membership hit.
• The concrete result is true.

Learning goal: Avoid the most common incorrect or unnecessarily slow solutions.

Core idea The central mistake is reaching for a nested loop: compare every pair and return when two values match. That works logically, but it performs up to O(n²) comparisons. A single set pass asks the same question—whether a value appeared earlier—without repeatedly revisiting old elements.

Algorithm plan

• Use one loop over nums.
• Keep seen outside the loop so it persists.
• Check membership before insertion.
• Return true on the first hit.
• Return false only after all values are processed.

Micro-example

• [8] has no opportunity for a pair, so return false.
• [3, 3] detects the second 3 immediately.
• [-2, 0, -2] works exactly like positive values; hashing is based on value equality.

Pitfalls

• Initializing seen inside the loop clears the history on every iteration.
• Returning false after the first unseen value is incorrect; later values may repeat.
• A set-based solution uses extra memory, so do not claim O(1) space.
• Sorting can be correct, but it is not the target linear-time approach.

Recap

• Preserve the set across the entire scan.
• Handle negative values and arrays of length one naturally.
• Prefer the linear set pass over quadratic pair checking.

Learning goal: State the performance guarantees and recognize the reusable pattern.

Core idea For an input of length n, the algorithm makes at most one membership check and one insertion per element before returning. Hash operations are O(1) on average, so the total expected running time is O(n). In the worst case, the set may hold every distinct input value, requiring O(n) additional space.

Algorithm plan

seen = set()
for value in nums:
    if value in seen:
        return True
    seen.add(value)
return False

The alternative size comparison, len(set(nums)) != len(nums), has the same expected O(n) time and O(n) space complexity, but the explicit loop makes early exit and the invariant easier to see.

Micro-example For [2, 5, 9, 1], four values are checked and inserted, then the loop ends. No membership hit occurs, so the result is false.

Pitfalls

• Say O(n) average time because hash-table operations are average-case bounds.
• Include the set when reporting auxiliary space.
• Do not report O(n²) just because a set is involved; each operation is not a full scan.

Recap

• Expected time: O(n).
• Auxiliary space: O(n).
• Reusable pattern: maintain a set of prior-seen values for fast membership tests.