Introduction

Contains duplicate is a very common problem in coding interviews. It is also a very simple problem to solve. In this blog post, we will see four different solutions to this problem.

Problem Statement

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.

more details on LeetCode

Exploring the problem

Before we start, let's see what the problem is asking us to do.

Basically, we need to check if any value appears at least twice in the given integer array.

If it does, we need to return true.

If it doesn't, we need to return false.

Example Code

This article is based on working code that you can find on GitHub.

Solution1 - Brute Force

The brute force solution is to iterate over the array and for each element, check if it appears again in the array.

class Solution1 {

    public boolean containsDuplicate(int[] nums) {
        for (var i = 0; i < nums.length; i++) {
            for (var j = 0; j < nums.length; j++) {
                if (i != j && nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

The containsDuplicate method uses nested loops to compare each element in the array with every other element. If there are duplicates, the method will return true, otherwise it will return false. Space complexity is O(1). But, this solution has a time complexity of O(n^2), which means it can become slow for large arrays.

Solution2 - Using hash map

Now, let's see how we can use a hash map to solve this problem.

class Solution3 {

    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (var num : nums) {
            var count = map.getOrDefault(num, 0);
            map.put(num, ++count);
        }
        for (var entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                return true;
            }
        }
        return false;
    }
}

This code uses a HashMap to store the count of each element in the input array nums. For each element, the map.getOrDefault(num, 0) method is used to retrieve the count of that element from the map. If the element is not in the map, it returns 0. The map.put(num, ++count) method is then used to increment the count of that element in the map. After iterating through the entire array, the code then iterates through the entries in the map and checks if any of the counts are greater than 1. If it finds an element with a count greater than 1, it returns true, indicating that the array contains duplicates. If it finishes iterating through the map without finding any duplicates, it returns false.

This approach has a time complexity of O(n) because it only processes each element in the array once, and a space complexity of O(n) because it stores the count of each element in a map, which can have a maximum size of n.

Solution3 - Using sorting

Let's see how we can use sorting to solve this problem.

class Solution3 {

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

}

Here, the Arrays.sort() method to sort the input array nums. Then, it iterates over the array and compares each element with its next element. If there are any equal elements, the method returns true, indicating that the array contains duplicates. If the loop finishes without finding any duplicates, the method returns false. This approach has a time complexity of O(n log n) due to the sorting, but it has a space complexity of O(1) as the sorting is performed in-place and no additional data structures are used.

Solution4 - Using hash set

Let's see first how we can use a hash set to solve this problem.

class Solution4 {

    public boolean containsDuplicate(int[] nums) {
        var sets = new HashSet<>(nums.length);
        for (var num : nums) {
            if (sets.contains(num)) {
                return true;
            }
            sets.add(num);
        }
        return false;
    }

}

In this code, a HashSet named set is created. Then, the input array nums is iterated, and for each element, the set.contains(x) method is called to check if the element is already in the set. If it is, the method returns true, indicating that the array contains duplicates. If the loop finishes without finding any duplicates, the method returns false.

This approach has a space complexity of O(1) because the size of the HashSet is limited to the length of the input array, and a time complexity of O(n) because each element is only processed once during the loop.

Conclusion

As you can see, there are many ways to solve this problem. But, the best solution is by using a hash set to solve this problem depending on the problem statement and constraints.