Problem statement
This problem is from Leetcode – Contains Duplicate. Problem statement is given below:
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.
Solution
Approach-1
Lets try a simple nested for loops approach. For each integer iterate the rest of the array to check whether another such integer exists.
See the code sample below:
public boolean containsDuplicate(int[] nums) {
boolean flag = false;
// iterate the array for each integer
for(int i=0; i<nums.length-1; i++) {
int curNum = nums[i];
// check if it occurs again
for(int j=i+1; j<nums.length; j++) {
// if yes then set the flag to true and return
if(curNum == nums[j]) {
flag = true;
return flag;
}
}
}
// else return false
return flag;
}Time complexity of this approach is O(N^2). You can check out the code from Github here: Contain Duplicate – First Approach.
Approach-2
Now lets try another approach with HashSet. Iterate the array and insert into a HashSet. While inserting check if the integer already exists in the HashSet. If it exists then return with true. See the code sample below:
public boolean containsDuplicate(int[] nums) {
boolean flag = false;
// initialize a HashSet
Set numsSet = new HashSet<>();
// insert the array integers in it
for(int i=0; i<nums.length; i++) {
// check if integer already exists in Hashset
if(!numsSet.contains(nums[i] ) ) {
numsSet.add(nums[i]);
}
else {
// if it exists then return with true
flag = true;
return flag;
}
}
return flag;
}
Time complexity of this approach is O(N). You can check out the code from Github here: Contain Duplicate – Second Approach.
See the runtime performance of this approach below:
