Do you think IIT Guwahati certified course can help you in your career?
Introduction
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
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
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.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int nums[n];
for(int i=0; i<n; i++){
cin>>nums[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.
if(nums[index]<0){
resultSet.push_back(index+1);
}
//Flip the number to negative
nums[index]=nums[index]*-1;
}
//return answer
for(int i=0; i<resultSet.size(); i++){
cout<<resultSet[i]<<" ";
}
}
You can also try this code with Online C++ Compiler
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.
Conclusion
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.
18+ registered 
