Problem:
Given an array of numbers , find if there are any duplicates
Input:
numbers = [ 4, 7, 3, 9, 3]
Output:
true, since 3 is present twice
Assumptions:
The number of elements in the array can be from 1 to a lakh.
The elements can be in the range of – 1 billion to + 1 billion
Try out the solution here:
https://leetcode.com/problems/contains-duplicate/
Solution:
The brute force solution is to iterate through the array and for each element check other elements in the array if they both match.
This requires two for loops and the time complexity is O(n2 ).
An optimal solution can be done in O(n) with an additional storage.
Hint:
Use an additional data structure to keep track of elements traversed
Optimal Solution:
Algorithm:
STEP1: Initialize an empty Hash Map
STEP2: Iterate through each element in the array
STEP3: For each element in the array check if the element already exists in the Hash Map , if it exists return true
STEP4: If element doesn’t exist , store the element as key and value as 1
STEP5: Return false if there are no duplicates as identified in STEP 3
Code:
class Solution {
public boolean containsDuplicate(int[] nums) {
var counterMap = new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(counterMap.containsKey(nums[i])){
return true;
}else{
counterMap.put(nums[i],1);
}
}
return false;
}
}
That’s it!
Leave a Reply