Check If an Array Contains Any Duplicate
Solve this Problem
Given an array
nums, return true if any value appears at least twice, and false if every element is distinct.
Checking every pair works but revisits the same information repeatedly. A hash setHash SetA collection that supports checking whether a value is present, and adding a new value, both in average O(1) time — no scanning required. remembers every value seen so far, so each new number only needs a single O(1) lookup to know whether it's already appeared — turning the O(n²) comparison into a single O(n) pass.
Test Case 1:
Input:nums = [1, 2, 3, 1]
Output:true
Explanation:The value 1 appears at index 0 and again at index 3.
Test Case 2:
Input:nums = [1, 2, 3, 4]
Output:false
Explanation:Every value is distinct.
Test Case 3:
Input:nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output:true
Explanation:Several values repeat — only one duplicate needs to be found.
Constraints
- ◆
1 ≤ nums.length ≤ 10⁵ - ◆
-10⁹ ≤ nums[i] ≤ 10⁹
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public boolean containsDuplicate(int[] nums) { |
| 3 | Set<Integer> seen = new HashSet<>(); |
| 4 | for (int num : nums) { |
| 5 | if (!seen.add(num)) return true; |
| 6 | } |
| 7 | return false; |
| 8 | } |
| 9 | } |
| 10 |
Array
1
2
3
1
0
1
2
3
↑i
HashMap
map.has(1)?✗ no
empty
Variables
i
0num
1LOOKUP
Check the set for 1. It's empty — nothing there yet.
Step 1 / 7
Approach & Solutions
Brute Force
BruteCompare every pair of elements. Correct, but re-checking pairs that share no relationship to a value already ruled out wastes time a single pass with memory could avoid.
Time
O(n²)Space
O(1)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]) return true;
6 }
7 }
8 return false;
9 }
10}Optimal — Hash Set
OptimalWalk the array once, trying to add each number to a hash set. If a number is already in the set, it's a duplicate — return true immediately. Otherwise add it and keep going.
Time
O(n)Space
O(n)Java
1class Solution {
2 public boolean containsDuplicate(int[] nums) {
3 Set<Integer> seen = new HashSet<>();
4 for (int num : nums) {
5 if (!seen.add(num)) return true;
6 }
7 return false;
8 }
9}