Contains Duplicates
Introduction
Given an integer array nums
true
false
Example 1
Output: true
Explanation: "1" repeated twice.
Example 2
Output: true
Explanation: all numbers in array are distinct.
Contents
Solution 1 - Using brute force approach
In this approach, in a nested for loop, we will check that every number at index i
nums
i+1
n
nums
-
We will create a function
that takes input arraybruteForceApproach
and returns anums
valueboolean
if a duplicate is found andtrue
otherwise.false
public class ContainsDuplicates {
/* brute force approach */
static boolean bruteForceApproach(int[] nums) {
for(int i=0; i<nums.length; i++) {
for(int j= i+1; j<nums.length; j++) {
if(nums[i] == nums[j]) {
return true;
}
}
}
return false;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n2) time where n
nums
nums
Space complexity: O(1) since we are only doing a numbers comparision and returning true or false.
Solution 2 - Using sorting approach, sort elements first, then check any two consecutive elements are same
In this approach, we we will sort the input array as first step, then loop through the elements of sorted array, and check if any two consecutive elements are same or not,
if any two are same return true
false
import java.util.Arrays;
import java.util.HashSet;
public class ContainsDuplicates {
/* using sorting approach */
static boolean usingSortingApproach(int[] nums) {
Arrays.sort(nums); // O(n log n)
for(int i=1; i<nums.length; i++) {
if(nums[i] == nums[i-1]) {
return true;
}
}
return false;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n log (n)) time where n
nums
nums
Space complexity: O(1), assuming that sorting will be using an in-place
Solution 3 - using HashSet to keep track of numbers
In this approach, we are going to use a HashSet
nums
As we loop through nums
true
false
import java.util.HashSet;
public class ContainsDuplicates {
/* Using hashset, store values into set and check if duplicate exists before putting a number into it */
static boolean usingHashSet(int[] nums) {
HashSet<Integer> cache = new HashSet<>();
for(int i=0; i<nums.length; i++) {
if(cache.contains(nums[i])) {
return true;
}
cache.add(nums[i]);
}
return false;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n
nums
Space complexity: O(n) since we are caching numbers into HashSet
Above implementations source code can be found at