Contains Duplicate

Easy Problem 2 of 151 Java and Python

Problem

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

Example 1

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

Example 2

Input: nums = [1, 2, 3, 4]
Output: false
Why: All four values are different.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Explanation

Duplicates are easy to spot when equal values sit next to each other, which is what sorting does.

Even better, a hash set remembers every value seen so far, so the moment you meet a value already in the set you have your answer.

Approach 1 · Naive

Sort and compare neighbours

Time O(n log n)
Space O(1) extra (O(log n) for the sort)

After sorting, any duplicate values are adjacent, so one scan comparing each element with the previous one finds them.

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

Java

import java.util.*;

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

Python

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

Approach 2 · Optimal

Hash set

Time O(n)
Space O(n)

Add each number to a set. If it is already there, it is a duplicate.

Create an empty set.
For each number, return true if it is in the set; otherwise add it.
Return false after the loop.

Java

import java.util.*;

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

Python

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

Complexity compared

Approach	Time	Space
Naive Sort and compare neighbours	O(n log n)	O(1) extra (O(log n) for the sort)
Optimal Hash set	O(n)	O(n)

Key takeaways

In Java, Set.add returns false when the value is already present, which saves a separate lookup.
Sorting trades memory for time: no extra structure, but O(n log n).

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem