1.Contains Duplicate

EasyBlind 75Arrays & Hashing · 1/9

Problem

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

Input:  nums = [1, 2, 3, 1]
Output: true
Explanation: The value 1 appears at index 0 and index 3.

Input:  nums = [1, 2, 3, 4]
Output: false
Explanation: Every element is distinct.

Input:  nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: true

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

💡 Key Insight

We only need to know whether we have seen a value before. Comparing every pair is slow, sorting puts duplicates next to each other, and a hash set answers "have I seen this?" in O(1) — so a single pass is enough.

Brute Force

TimeO(n²)SpaceO(1)

Intuition

Compare every element with every element that comes after it. If any pair is equal, we found a duplicate.

Algorithm

For each index i from 0 to n - 1:
For each index j from i + 1 to n - 1:
If nums[i] == nums[j], return true.
If no pair matched, return false.

Visualization

nums = [1, 2, 3, 1]

i=0 (1): compare with 2 ✗, 3 ✗, 1 ✓  → return true

Code

java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return true; // found a pair of equal values
                }
            }
        }
        return false;
    }
}

Complexity

Time: O(n²) — every pair (i, j) is checked once.
Space: O(1) — no extra data structures.

Sorting

TimeO(n log n)SpaceO(1) to O(n)

Intuition

After sorting, equal values become adjacent. So we only need to compare each element with its neighbour.

Algorithm

Sort nums.
For i from 1 to n - 1, if nums[i] == nums[i - 1] return true.
Return false.

Visualization

original: [1, 2, 3, 1]
sorted:   [1, 1, 2, 3]
           ^  ^
           equal neighbours → true

Code

java

import java.util.Arrays;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums); // duplicates become neighbours
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O(n log n) — dominated by sorting.
Space: O(1) to O(n) — depends on the sort implementation (Java's dual-pivot quicksort uses O(log n) stack).

Hash SetOptimal

TimeO(n)SpaceO(n)

Intuition

A HashSet stores the values we have already visited. Before inserting a value, check whether it is already present — if it is, that value is a duplicate. HashSet.add conveniently returns false when the element already exists.

Algorithm

Create an empty HashSet<Integer> seen.
For each num in nums:
- If seen already contains num, return true.
- Otherwise add num to seen.
Return false.

Dry Run

flowchart LR
    A["num = 1<br/>seen = {}"] -->|"add 1"| B["num = 2<br/>seen = {1}"]
    B -->|"add 2"| C["num = 3<br/>seen = {1,2}"]
    C -->|"add 3"| D["num = 1<br/>seen = {1,2,3}"]
    D --> E{"1 in seen?"}
    E -->|"yes"| F["return true"]

Code

java

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

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            // add() returns false if num was already in the set
            if (!seen.add(num)) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O(n) — each element is inserted / looked up once in O(1) average.
Space: O(n) — in the worst case (all distinct) the set holds every element.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Sorting	O(n log n)	O(1)–O(n)
Hash Set	O(n)	O(n)

Common Pitfalls

Using List.contains instead of a Set — that makes each lookup O(n) and the whole solution O(n²).
Sorting modifies the input array; mention this trade-off if the caller needs the original order.
Forgetting that nums can contain negative numbers — a fixed-size boolean array indexed by value will not work.
Returning early with false inside the loop — you can only conclude "no duplicates" after scanning everything.