Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Problem Statement
Naive Approach
Optimized Approach
Complexity Analysis
Frequently Asked Questions
How to approach a problem like this?
What is HashSet?
What is the difference between Array and Vector?
Last Updated: Mar 27, 2024

Find All Duplicates in an Array

Author Urwashi Priya
0 upvote
Crack Google SDE interview : Essential projects
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM


Arrays are important data structures that are also elementary in nature as well. They are very useful in nature and mastery of them could help solve a lot of problems. Arrays are basically a collection of data. 

Problem Statement

The problem is to Find All Duplicates in an Array.

We are given an array of N elements, and each integer appears once or twice. We have to return an array of all the integers that appears twice.

Example: nums = [4,3,2,7,8,2,3,1]

Here, 2 and 3 appear twice.

∴The output will be [2,3]

Recommended: Try the Problem yourself before moving on to the solution

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job

Naive Approach

The naive approach to Find All Duplicates in an Array will be to take each element and to find whether any second occurrence of that element is present in the entire array or not. If any second occurrence is present, then we need to display it in the answer array. But this approach would take O(n²) time.

To have an optimized approach, we can also do this by using a HashSet.

This would reduce our Time Complexity and space complexity to O(n).


Declare a HashSet

If an element is not present in the HashSet on traversing the array, add the element to HashSet.

 If that element is present in the HashSet, add the element to the result array.

Return the result array.


Optimized Approach

As the condition to us is 1 <= nums[i] <= n, this means that number present in the array will not be greater than the length of the array so that we can reduce our space complexity to O(1).


get the index; the element corresponds to

Flip the number to negative

If the number is already negative, we encounter it twice, so store it in the answer array.

Return answer. i.e.:All Duplicates in an Array

illustration image

So in the most optimal approach, the time complexity for this problem will reduce to O(n) and space complexity to O(1).

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

Find All Duplicates In An Array

If you were not able to solve it, don’t be sad. It’s a part of the learning process.

Please have a look at the algorithm, and then again, you must give it a try.




procedure findDuplicates( ):


1.   Declare a vector to store the answer.

2.   Run a for loop from 0 till the size of nums.

3.   index=abs(nums[i])-1

4.   if(nums[index]<0)

5.   Store the number in the answer array.

6.   Else nums[index]=nums[index]*-1;

7.   Return the answer.


end procedure



#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	int nums[n];
	for(int i=0; i<n; i++){
	//vector to store answer array
	vector<int> resultSet;   
	for(int i=0; i<n; i++){            
		//get the index, the element corresponds to
		int index=abs(nums[i])-1;         
		//if present number is already negative, it means we are encountering it twice, so store in answer array.
		//Flip the number to negative
	//return answer 
	for(int i=0; i<resultSet.size(); i++){
		cout<<resultSet[i]<<" ";



Sample Input: 
Sample Output:

Complexity Analysis

Check out Time and Space Complexity

Time Complexity: O(n).

Analyzing Time Complexity:

Since the loop runs only once.


Space complexity: O(1) since no extra variable is used.

Check out this problem - Find Duplicate In Array

Frequently Asked Questions

How to approach a problem like this?

First, understand the problem. The best way is to use diagrams. Then write your algorithm. Then start with the Brute Force method. Lastly, try to optimize your code.

What is HashSet?

Unordered collections consisting of unique elements is referred to as HashSet. To know more about HashSet, click here.

What is the difference between Array and Vector?

The array is static in size, whereas the vector is dynamic in size. 


This article taught us how to Find All Duplicates in an Array by approaching the problem using a hash set and then without extra space. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most binary search tree problems.
Now, we recommend you practice problem sets based on arrays to master your fundamentals. You can get a wide range of questions similar to this on Coding Ninjas Studio

It's not the end. Must solve the problem of similar types.

Recommended Reading:

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Happy Coding.

Previous article
Count Items Common to Both the Lists But With Different Prices
Next article
Find Number of Employees Under Every Manager
Live masterclass