Contains Duplicate [LeetCode Top Interview Questions Series]

“Contains Duplicate” is a common problem in computer science, often used to introduce arrays or hash tables. The problem statement is as follows:

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example: Input: [1,2,3,1] Output: true

Input: [1,2,3,4] Output: false

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

In this solution, we use a HashSet to keep track of the elements we have seen so far. For each element in the input array, we check if it is in the set. If it is, we return true as we have found a duplicate. If we reach the end of the array without finding any duplicates, we return false

The time complexity of the solution is O(n), where n is the number of elements in the input array nums. This is because we iterate over all elements in the array once and perform constant-time set operations (addition and containment check) on each iteration.

The space complexity of the solution is O(n), where n is the number of elements in the input array nums. This is because we use a HashSet to store all the elements in the array, and the size of the set is at most n.

Can we do it without extra space ?

it’s possible to solve the “Contains Duplicate” problem without using extra space by sorting the array first, then checking for duplicates in a single pass. Here’s an example implementation in 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;
}
}

In this implementation, we sort the input array nums using the Arrays.sort method. After sorting, we can easily check for duplicates by comparing adjacent elements in the sorted array. If we find any duplicates, we return true immediately. If we reach the end of the array without finding any duplicates, we return false.

The time complexity of this solution is O(nlogn) due to the sorting step, and the space complexity is O(1), since we are not using any extra data structures to store the elements of the array.