Contains Duplicate - LeetCode Java Solution

Hello readers, let’s solve a LeetCode problem today.

In this blog, let’s solve Contains Duplicate which is one of the Blind 75 List of LeetCode Problems.

This is a very good LeetCode Easy problem for beginners.

There are multiple potential solutions for this problem, which we will go through in this blog.

Understand the Problem

The Objective of the problem is to Determine if an array contains any duplicate values

In the Problem Description, it is given:

• Given an array of numbers: nums
• Return true if there are any values in the array that appear at least twice
• Return false if all values in the array are distinct

Understand the Testcases

To understand the problem better, three examples are given:

In Example 1, it is given:

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

Here, we can spot there are two ones 1 at the first and last index and hence 1 is the duplicate value in this array. So, we can return the output true.

In Example 2, it is given:

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

Here, we can see that all four numbers are distinct values in this array. So, we can return the output false.

In Example 3, it is given:

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

Here, we can see many duplicate values of the numbers 1,2,3 and 4 in this array. So, we can return the output true.

Brute Force Approach

The brute force approach will be to compare each number with every other number in the array until we find the duplicate number.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for(int i=0;i<nums.length; i++) {
            for(int j=i+1; j<nums.length; j++) {
                if(nums[i] == nums[j]) { 
                    // found the duplicate
                    return true;
                }
            }
        }
        return false;
    }
}

Here are the key points to understand the code:

• This approach follows a brute force method of comparing each number with every other number in the array to find duplicates.
• We use nested loops to traverse through all possible pairs of elements in the array.
• The outer loop iterates over each element in the array, and the inner loop compares that element with the remaining elements.
• If any two elements are found to be equal, it means we have found a duplicate value, and we return true.
• After comparing all possible pairs and not finding any duplicates, we return false.

Time complexity:

• The time complexity of this approach is O(N^2), where N is the number of elements in the 'nums' array. This is because we have nested loops, causing us to compare each element with every other element in the worst case.

Space complexity:

• The space complexity of this approach is O(1) because it does not require any additional space that grows with the input size.

Better Approach:

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

Here are the key points to understand the code:

• This approach takes advantage of sorting the array first to simplify the duplicate checking process.
• The array is sorted in ascending order using the Arrays.sort() method.
• By sorting the array, duplicate elements become adjacent to each other, making it easier to identify duplicates by comparing adjacent elements.
• We traverse the sorted array and compare each element with its next adjacent element.
• If any adjacent elements are equal, it means we have found a duplicate value, and we return true.
• If no duplicates are found after checking all adjacent pairs, we return false.

Time complexity:

• The time complexity of this approach is O(N * log(N)), where N is the number of elements in the 'nums' array. This is because sorting the array takes O(N * log(N)) time using efficient sorting algorithms like Merge Sort or Quick Sort.

Space complexity:

• The space complexity of this approach is O(log(N)), where N is the number of elements in the 'nums' array. This space is used for the recursive calls in the sorting algorithm.

Java Solution (Using HashSet):

• We can use a HashSet to efficiently check for duplicates in the given array.
• HashSet is a data structure that stores unique elements. It allows for constant-time (O(1)) operations like adding and searching for elements.

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

Here are the key points to understand the code:

• We traverse the 'nums' array and for each element 'n', we check if it is already present in the HashSet.
• If the value is present, it means we have found a duplicate, so we return true.
• If the value is not present, we add it to the HashSet to keep track of unique elements.
• After traversing the entire array and not finding any duplicates, we return false.

Time complexity:

• The time complexity of this solution is O(N), where N is the number of elements in the 'nums' array. This is because we traverse the entire array once.

Space complexity:

• The space complexity of this solution is O(N), where N is the number of elements in the 'nums' array. This is because in the worst case, all elements in the array could be unique and stored in the HashSet.

Java Solution (Using HashMap):

• We can use a HashMap to efficiently check for duplicates in the given array.
• HashMap is a data structure that stores key-value pairs, where each key is unique.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Boolean> dups = new HashMap<>();        
        for (int n : nums) {
            if (dups.containsKey(n)) {
                return true;
            }            
            dups.put(n, true);
        }        
        return false;
    }
}

Here are the key points to understand the code:

• We traverse the 'nums' array and for each element 'n', we check if it is already a key in the HashMap.
• If it is a key, it means we have found a duplicate value, so we return true.
• If the element is not present as a key, we add it to the HashMap with a value of 'true' to keep track of its presence.
• After traversing the entire array and not finding any duplicates, we return false.

Time complexity:

• The time complexity of this solution is O(N), where N is the number of elements in the 'nums' array. This is because we traverse the entire array once.

Space complexity:

• The space complexity of this solution is O(N), where N is the number of elements in the 'nums' array. This is because in the worst case, all elements in the array could be unique and stored as keys in the HashMap.

Conclusion

• The brute force solution has a time complexity of O(N^2) but no extra memory usage.
• Sorting the array improves the time complexity to O(N * log(N)) but still requires no extra memory.
• Using a HashMap & HashSet offers the best time complexity of O(N) but requires additional memory.

NeetCode Solution Video:

https://www.youtube.com/watch?v=3OamzN90kPg

Recommended Resources to Learn Data Structures and Algorithms

Basics of DS Algo Blogs:

1. Hashing in Java

Recommended YouTubers for LeetCode Problems:

1. NeetCode
2. Take U Forward

Free Resources for Learning Data Structures and Algorithms:

1. NeetCode Roadmap
2. Striver’s SDE Sheet

Recommended Courses for Learning Data Structures and Algorithms:

1. NeetCode Courses
2. ZTM: Mastering the Coding Interview (Big Tech): Available on Udemy and ZTM Academy
3. ZTM: Mastering the Coding Interview: Available on Udemy and ZTM Academy
4. Data Structures & Algorithms, Level-up for Coding Interviews Course
5. Striver’s A2Z (Free) Course

Top Coursera Courses for Learning Data Structures and Algorithms:

1. Coding Interview Preparation (Meta)
2. Algorithms Course Part I (Princeton University)
3. Algorithms Course Part II (Princeton University)
4. Data Structures and Algorithms Specialization (UC San Diego)
5. Algorithms Specialization (Stanford)

(Note: The Coursera courses can be audited to get free access to the lectures)

🎙 Disclosure: Please note that some of the links mentioned on this page may be affiliate links. This means that if you click on one of these links and make a purchase, I may earn a small commission from the sale.

Who Am I?

I’m Aswin Barath, a Software Engineering Nerd who loves building Web Applications, now sharing my knowledge through Blogging during the busy time of my freelancing work life. Here’s the link to all of my craziness categorized by platforms under one place: https://linktr.ee/AswinBarath

Keep Learning

Now, I guess this is where I say goodbye 👋. But, hey it’s time for you to start learning with your newfound Knowledge(Power)👨‍💻👩‍💻. Good Job that you made it this far 👏 & Thank you so much for reading my Blog 🙂.