Skip to content

217. Contains Duplicate

Solutions

Language Approach Time Space File
java Set O(n) O(n) java/SetSolution.java
java Sort O(n log(n)) O(1) java/SortSolution.java
python Set O(n) O(n) python/set_solution.py
python Sort O(n log(n)) O(1) python/sort_solution.py

Set — java

Time: O(n)
Space: O(n)

java/SetSolution.java
// Time: O(n)
// Space: O(n)

import java.util.HashSet;

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

Sort — java

Time: O(n log(n))
Space: O(1)

java/SortSolution.java
// Time: O(n log(n))
// Space: O(1)

import java.util.Arrays;

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

Set — python

Time: O(n)
Space: O(n)

python/set_solution.py
# Time: O(n)
# Space: O(n)

from typing import List

from task import Task


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

Sort — python

Time: O(n log(n))
Space: O(1)

python/sort_solution.py
# Time: O(n log(n))
# Space: O(1)

from typing import List

from task import Task


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

Traces

Set

Set trace

Step 1
idx: 0 1 2 3
val: 1 2 3 1
   ^
set: []
Step 2
idx: 0 1 2 3
val: 1 2 3 1
     ^
set: 1
Step 3
idx: 0 1 2 3
val: 1 2 3 1
       ^
set: 1 2
Step 4
idx: 0 1 2 3
val: 1 2 3 1
         ^
set: 1 2 3
Step 5
idx: 0 1 2 3
val: 1 2 3 1
           ^
set: 1 2 3
     ^
output: true

Sort

Sort trace

Step 1
idx: 0 1 2 3
val: 1 2 3 2
   ^
Step 2
idx: 0 1 2 3
val: 1 2 2 3
   ^
Step 3
idx: 0 1 2 3
val: 1 2 2 3
       ^
1 != 2
Step 4
idx: 0 1 2 3
val: 1 2 2 3
         ^
1 != 2
2 == 2
output: true