# Find Duplicate Element

In this lesson, you will learn how to find the duplicate element using a hashing algorithm.

## Problem statement

Given an array of integers `A`, find one number that repeats. Find the repeated element and return it. If there are no duplicate elements present in the input array, return `-1`.

## Examples

Example 01:

``````Input: A = [3, 4, 1, 4, 2]

Output: 4``````

Example 02:

``````Input: A = [-7, 19, 1, 4, 2]

Output: -1``````

Example 03:

``````Input: A = [1, 1, 4, 2, 1]

Output: 1 // 1 appeared 3 times in the array``````

## Thought process

Before writing pseudo code, come up with questions and ask the interviewer.

1. Is the input array sorted?
2. Should we return `-1`, when the input array is empty?

## Algorithm

1. Create a `HashSet` and store the first element.
2. Iterate through all the elements.
3. Check if they exist in the `HashSet`; if yes, return the element. If not, store the element in the `HashSet`.
4. Continue the process until the last iteration. If there is no repeating element, return `-1`.

## Solution

``````import java.util.HashSet;

public class FindDuplicateElement {
public static void main(String[] args) {
int[] A = {-7, 5, 1, 4, 2, 2};

System.out.println(findDuplicate(A));
}

private static int findDuplicate(int[] A) {
HashSet<Integer> uniqueElements = new HashSet<>();

for (int el : A) {
if (uniqueElements.contains(el)) {
return el;
}

}
return -1;
}
}
``````

## Complexity analysis

Time complexity: `O(n)`, we need to traverse all the elements in the array. If there are `n` items, then the time complexity to run the algorithm takes `O(n)`.

Space complexity: `O(n)`, this is because we are storing `n` elements in the `HashSet`.

Coding Interview QuestionsArraysData Structures and Algorithms

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!