leetcode-textbook

0217 - Contains Duplicate

Difficulty: Easy Pattern: Arrays & Hashing LeetCode: https://leetcode.com/problems/contains-duplicate/

Concepts used

Problem

Given an integer array nums, return true if any value appears at least twice in the array, and false if every element is distinct.

Signature:

boolean containsDuplicate(int[] nums)

Examples:

Input:  nums = [1,2,3,1]
Output: true      # 1 appears twice

Input:  nums = [1,2,3,4]
Output: false     # every element is distinct

Intuition

Imagine you’re a teacher checking a tall stack of homework for two identical papers. You could compare every paper against every other paper, but with 100 papers that is thousands of comparisons. Far better: flip through the stack once, and for each paper ask “have I already seen this exact name on my list?” The first time the answer is “yes”, you’ve caught a duplicate and can stop.

Walk the smallest case, nums = [2, 5, 1, 5]. Read 2 – never seen it, jot it down. Read 5 – new, jot it. Read 1 – new, jot it. Read 5 again – 5 is already on the list, so the answer is true.

The general rule follows the same shape. Keep a notebook that answers “have I seen this?” in no time at all. In code that notebook is a hash set – a container built so that “is X in here?” is answered in O(1), as fast as recognizing a familiar face. Walk the array once (a linear scan); at each value, ask the set whether the value is already inside. The first “yes” is your duplicate. Reach the end with every value new, and there are none.

Why O(n) and not O(n^2)? Because the set check costs O(1), not O(n). The slow alternative – a second inner loop comparing each element against all earlier ones – does roughly n/2 + n/3 + ... comparisons; the hash set lets each element settle its question with a single constant-time check.

Checkpoint A – Spot the data structure

Pause and pick before expanding. A wrong first guess teaches more than a fast right one.

Q1 (recall). This problem keeps asking “have I seen this value before?” Which container is built exactly for that?

Show answer **(b)** -- a hash set answers membership ("is X in here?") in O(1). Option (a) needs a sort first, and (c) is the O(n^2) brute force.

Q2 (comprehend). Why is the hash-set solution O(n) and not O(n^2)?

Show answer **(b)** -- one pass of n steps, each step one O(1) lookup. The O(n^2) version comes from replacing that O(1) lookup with an inner scan of all earlier elements.

Pseudocode

function containsDuplicate(nums):
    create an empty set called "seen"
    for each value x in nums:
        if x is already in seen:
            return true          # second sighting -> duplicate
        add x to seen
    return false                 # finished the loop, everything was distinct

Java Solution

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (seen.contains(x)) {
                return true;
            }
            seen.add(x);
        }
        return false;
    }
}

We use a HashSet (not a HashMap) because we store only values, never data attached to them. Membership is checked with contains(x) before add(x) so the current element is never matched against itself – harmless here, but the habit matters for Two Sum. The early return true exits the instant a duplicate appears, so the average case is much faster than a full scan. The default return false after the loop cleanly handles the empty and single-element inputs.

Complexity

Time:  O(n)  -- one pass; each contains/add is O(1) average on a HashSet
Space: O(n)  -- worst case (all distinct) the set holds every element

Dry-Run

Input nums = [2, 5, 1, 5]:

Step x seen (before) Action seen (after) Result
1 2 {} 2 not seen; add {2} -
2 5 {2} 5 not seen; add {2, 5} -
3 1 {2, 5} 1 not seen; add {1, 2, 5} -
4 5 {1, 2, 5} 5 IS seen - true

Output: true.

Checkpoint B – Trace and stress it

Q1 (apply). Trace nums = [3, 1, 3]. What is returned, and at which step does the loop stop?

Show answer **(b)** -- step 1 adds 3 -> {3}; step 2 adds 1 -> {1,3}; step 3 reads 3, which IS in the set, so we `return true` immediately. The loop never reaches a fourth step.

Q2 (analyze). What should containsDuplicate([]) return, and why does the code handle it with no special case?

Show answer **(b)** -- an empty array has no pairs, so "no duplicates" is correct. The for-each loop iterates zero times and control reaches the trailing `return false`.

Q3 (transfer). Suppose instead of true/false you had to return the FIRST value that repeats. What is the smallest change to the current code?

Show answer Replace `return true;` with `return x;` (change the return type to `int` and use a sentinel like `-1` for "no duplicate"). The check-before-add order already finds the first repeat at its second sighting.

Common mistakes