Find All Duplicates in an Array | Clean | Easy | Leetcode 442 | codestorywithMIK

This is the 87th Video of our Playlist "Arrays 1D/2D : Popular Interview Problems".

In this video we will try to solve an extremely good problem :
Find All Duplicates in an Array | Clean | Easy | Leetcode 442 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Find All Duplicates in an Array | Clean | Easy | Leetcode 442 | codestorywithMIK
Company Tags : Pocket Gems, Amazon, Meta

Approach Summary :
The given approach is designed to find duplicates in an array of integers efficiently. It works by utilizing the properties of the array itself to mark visited elements.
Here's how the approach works:
1. Iterate through each element of the input array `nums`.
2. For each element `num`, take its absolute value (`abs(nums[i])`) to ensure positive index access.
3. Check if the element at index `num - 1` (assuming 1-based indexing) is negative. If it is negative, it means `num` has been encountered before, so it's a duplicate. In this case, add `num` to the result vector.
4. If the element at index `num - 1` is not negative, mark it as visited by multiplying it by -1 (`nums[num - 1] *= -1`). This indicates that `num` has been encountered.
5. Repeat steps 3-4 for all elements in the array.
6. Return the result vector containing duplicates.
This approach effectively utilizes the sign of the elements in the input array to mark visited elements, making it a space-efficient solution with a time complexity of O(n), where n is the size of the input array.

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

✨ Timelines✨
00:00 - Introduction
01:24 - Brute Force 1 and Brute Force 2
02:43 - Optimal Approach
10:33 - Coding it up

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024

[codestorywithMIK]

Happy Holi everyone ❤❤
Enjoy and spend time with your family. 🎉🎉❤️❤️

[thegreekgoat]

What a legend yaar. Pity of those who dont know about this channel. Absolute gem

[KrishnaGupta-kdjh]

The way you teach is absolutely great, sir. Please do not stop uploading these series ....

[shraban]

Thank u sir for explaining in such a elegant manner. Your channel is my one stop solution for leetcode probs understanding.

[oqant]

Last approach was lit 🔥🔥
Thanks ❤❤
POTD DONE [25.3.24]✅✅

[MohitKumar-yxhr]

thank you for giving such kind of different approach to solve the problem in simple way 🙏❤💯

[iWontFakeIt]

swap sort se solve kiya but ye approach bhi acha ha socha tha maine iske bare mein <3

[KINGSLAYERAYT]

This question can be solved easily using cyclic sort

[retromonk]

i was struggling when value at any index becomes equal to size of array, thanks i got what i was doing wrong

[abcd]

I solved it coz i learnt this method from you in some other vdeos

[AnjuGupta-szuk]

Learnt one new concept ... Thanku so much Bhaiya

[onelove]

Simply apply cycling sort later run a loop which is not at their correct index that will be ans

[aditimahabole]

think of it as find cycle in link list

[nikhil_kolla_]

Good video, please check the description, the "Approach Summary" is not for this question.

[Sparkling_jelly]

for sorting approach why the time complexity is nlogn? and why not n+log(n) ??
also why did we push n and not nums[idx]*(-1)?

[naveenkumarkota]

mike we came up with 0(n) and 0(n) complexities will the interviewer be satisfied ? or he assume with those constraints its so easy?

[sjxsubham...]

sort(nums.begin(), nums.end());
vector<int> ans;
for(int i = 0; i< nums.size()-1; i++){
if(nums[i] == nums[i+1]{
ans.push_back(nums[i]);
}
}
return ans;



Easy solution 😄

[abhijitroy]

class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int maxi=INT_MIN;
for(auto it:nums){
maxi=max(maxi, it);
}
vector<int>v(maxi+1, 0);
vector<int>v1;
for(int i=0;i<nums.size();i++){
if(v[nums[i]]==0){
v[nums[i]]=1;
}else{
v1.push_back(nums[i]);
}
}
return v1;
}
};

can it be an optimal solution as i m taking const space ?

[dayashankarlakhotia]

good explanation please update link.🎉❤

[abhisheknishad]

brother . I have already done this but having a doubt is that why vector is not taking space in this ? isn't it O(n) space?
help me out