Contains Duplicate

Problem in Plain English

Given an integer array, decide whether any value appears at least twice. Return true when a repeat exists and false when every element is distinct.

Problem Statement

Given an integer array nums, return true when two different indices contain the same value. Return false when all values are distinct.

Only the existence of a repeat matters: you do not need its index, its frequency, or a modified array.

Constraints

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

Examples

Example 1

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

The value 1 appears at indices 0 and 3, so a duplicate exists.

Example 2

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

Every element appears exactly once, so there is no duplicate.

Example 3

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

Several values repeat, for example 1 appears three times.

Intuition

Imagine checking names at a door: each new arrival is compared with the names already checked in. In [1, 2, 3, 1], the first three values are new, but the final 1 is already on the list. A set stores distinct values and answers whether a value is present; it remembers the past without comparing every pair again.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Compare each element with every element after it. This uses no extra collection, but an array with no repeat forces every possible pair to be checked.

Step-by-Step Logic

For each index i, inspect only later indices j = i + 1 through the end. This excludes comparing an element with itself.
If nums[i] == nums[j], return true immediately. In Example 1, i = 0 fixes the value 1.
Compare it with 2 at index 1, then 3 at index 2; both differ. The next comparison with 1 at index 3 matches.
Return true for that matching pair. If every pair finishes without a match, return false.

Why It Works

Every two different indices have a unique order with the smaller one first, so the nested loops inspect every possible pair once. A matching pair proves a repeat exists. If no inspected pair matches, no two positions have equal values, so returning false is correct.

Dry Run

Brute Force: variable states at each step
`i`	`j`	`nums[i]`	`nums[j]`	result
`0`	`1`	`1`	`2`	no match, keep scanning
`0`	`2`	`1`	`3`	no match, keep scanning
`0`	`3`	`1`	`1`	match, return `true`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Let n be the array length. With no duplicates, the loops compare n(n - 1)/2 pairs, giving O(n^2) worst-case time; an early match can finish in O(1). Only the two indices are stored, so extra space is O(1). The input is unchanged.

Code

Solution.java

1class Solution {2    public boolean containsDuplicate(int[] nums) {3        for (int i = 0; i < nums.length; i++) {4            for (int j = i + 1; j < nums.length; j++) {5                if (nums[i] == nums[j]) {6                    return true;7                }8            }9        }10        return false;11    }12}

Hints

Hint 1

A repeated value must appear at two different positions. What would checking all pairs cost?

Hint 2

Instead of checking the whole past again, can you remember only which values have appeared?

Hint 3

Check a hash set before inserting each value. The first membership hit is enough to return true.

Edge Cases

One value, such as [7], returns false; two different indices are required. Empty arrays are outside the public constraints.
An immediate repeat, such as [2, 2, 2], returns true at the second value in the hash-set approach.
A late repeat, [1, 2, 3, 1], exercises checking the last element; [1, 2, 3, 4] requires scanning to the end.
Negative values and zero need no special rules: [-1, 0, -1] returns true.
Boundary values [-1000000000, 1000000000] are distinct. A Boolean array indexed by value would waste memory across this large range.

Common Mistakes and Interview Tips

Inserting into seen before checking membership makes every current value look repeated. Check first, then insert.
Starting the inner loop at j = i compares each element with itself and incorrectly returns true.
Using a list for seen makes membership O(n) and restores quadratic total time. A set answers presence directly; a frequency map stores information this question does not need.
Interview tip: state that hashing gives expected linear time and linear extra space. Sorting and checking neighbors is an O(n log n) alternative when memory trade-offs matter, but sorting in place changes the input and library sorting storage depends on the implementation.

Key Takeaway

For Arrays & Hashing questions about whether a value appeared earlier, a hash set turns repeated searches of the past into one expected linear scan. Keep a map instead when you also need counts or an earlier index.