Data Structures and Algorithms in Java – Arrays – Contains Duplicate

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!


Posted

in

,

by

Comments

Leave a Reply

Discover more from The Full Stack Developer

Subscribe now to keep reading and get access to the full archive.

Continue reading