Contains Duplicate - LeetCode Java Solution
Tags: java, datastructures, algorithms, leetcode
Published: 2023-08-11 10:36:07

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

In this blog, let’s solve [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) which is one of the [Blind 75 List of LeetCode Problems](https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions).

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.

```java
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:

```java
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.

```java
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.

```java
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](https://www.notion.so/Hashing-in-Java-63165e1d339e4ff0b4fa6c28fe24cd8c?pvs=21)

Recommended YouTubers for LeetCode Problems:

1. [NeetCode](https://www.youtube.com/@NeetCode)
2. [Take U Forward](https://www.youtube.com/@takeUforward/featured)

Free Resources for Learning Data Structures and Algorithms:

1. [NeetCode Roadmap](https://neetcode.io/roadmap?utm_source=aswin)
2. [Striver’s SDE Sheet](https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/)

Recommended Courses for Learning Data Structures and Algorithms:

1. [NeetCode Courses](https://neetcode.io/courses?utm_source=aswin)
2. ZTM: Mastering the Coding Interview (Big Tech): Available on [Udemy](https://click.linksynergy.com/link?id=JDofPMV5KuY&offerid=1060092.3919716491451706865583445&type=2&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fmaster-the-coding-interview-big-tech-faang-interviews%2F) and [ZTM Academy](https://academy.zerotomastery.io/a/aff_rml6679s/external?affcode=441520_dcwk-s8s)
3. ZTM: Mastering the Coding Interview: Available on [Udemy](https://click.linksynergy.com/link?id=JDofPMV5KuY&offerid=1060092.391976131953022569348758&type=2&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fmaster-the-coding-interview-data-structures-algorithms%2F) and [ZTM Academy](https://academy.zerotomastery.io/a/aff_nqb6sg6w/external?affcode=441520_dcwk-s8s)
4. [Data Structures & Algorithms, Level-up for Coding Interviews Course](https://click.linksynergy.com/link?id=JDofPMV5KuY&offerid=1060092.391975289945963380819471&type=2&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fcpp-data-structures-algorithms-levelup-prateek-narang%2F)
5. [Striver’s A2Z (Free) Course](https://takeuforward.org/strivers-a2z-dsa-course/strivers-a2z-dsa-course-sheet-2/)

Top Coursera Courses for Learning Data Structures and Algorithms:

1. [Coding Interview Preparation (Meta)](https://imp.i384100.net/QyNgyo)
2. [Algorithms Course Part I (Princeton University)](https://imp.i384100.net/KjqAe9)
3. [Algorithms Course Part II (Princeton University)](https://imp.i384100.net/VmbWyE)
4. [Data Structures and Algorithms Specialization (UC San Diego)](https://imp.i384100.net/g1AVOA)
5. [Algorithms Specialization (Stanford)](https://imp.i384100.net/75G7ag)

(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](https://medium.com/techsoftware) 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 🙂.