# 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!