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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s