Find All Duplicates in an Array | Clean | Easy | Leetcode 442 | codestorywithMIK
Vložit
- čas přidán 27. 07. 2024
- iPad PDF Notes - github.com/MAZHARMIK/Intervie...
Whatsapp Community Link : www.whatsapp.com/channel/0029...
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
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/find-al...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
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
Happy Holi everyone ❤❤
Enjoy and spend time with your family. 🎉🎉❤️❤️
Similar Pattern Qn - Leetcode-41 (Hard version of this pattern) - czcams.com/video/lyjOwaUEWWQ/video.htmlsi=ClWuoKanT2plI8zi
Happy Holi bhaiya ❤😊😊
Happy Holi bhaiya ❤️
Happy Holi ❤❤❤
Happy Holi Bhaiya😊
What a legend yaar. Pity of those who dont know about this channel. Absolute gem
The way you teach is absolutely great, sir. Please do not stop uploading these series ....
Thank u sir for explaining in such a elegant manner. Your channel is my one stop solution for leetcode probs understanding.
thank you for giving such kind of different approach to solve the problem in simple way 🙏❤💯
Last approach was lit 🔥🔥
Thanks ❤❤
POTD DONE [25.3.24]✅✅
swap sort se solve kiya but ye approach bhi acha ha socha tha maine iske bare mein
Learnt one new concept ... Thanku so much Bhaiya
I solved it coz i learnt this method from you in some other vdeos .....
This question can be solved easily using cyclic sort
Great work
i was struggling when value at any index becomes equal to size of array, thanks i got what i was doing wrong
Simply apply cycling sort later run a loop which is not at their correct index that will be ans
think of it as find cycle in link list
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)?
Good video, please check the description, the "Approach Summary" is not for this question.
Done❤️❤️
Happy holi sir
A very Happy Holi ❤️❤️
happy holi sir
A very Happy Holi brother ❤️❤️🙏🙏
@@codestorywithMIK sir your voice are little low in this video .. 😥😥😥😥
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?
That’s fine.
But it’s highly likely they will ask for optimised version if they have given you the constraints.
good explanation please update link.🎉❤
Done ❤️❤️
Happy Holi ❤❤
A very happy holi ❤️❤️
class Solution {
public:
vector findDuplicates(vector& nums) {
int maxi=INT_MIN;
for(auto it:nums){
maxi=max(maxi,it);
}
vectorv(maxi+1,0);
vectorv1;
for(int i=0;i
Actually this is not a constant space. The maximum value can be anything. So the size of array depends on maximum value.
@@codestorywithMIK thanks for confirming
Can anyone list questions following this pattern ?
Leetcode-41 (Hard version of this pattern)
Surprisingly it’s Today’s POTD - czcams.com/video/lyjOwaUEWWQ/video.htmlsi=ClWuoKanT2plI8zi
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
Actually we usually don’t consider the result data structure(which we have to return) in the space complexity.
Ohh.. Thanks
bhaiya are u in which company right now???
Know everything about me here - github.com/MAZHARMIK ❤️😇
i want the pdf please
iPad PDF Notes (Added in Description also) github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-442-Find%20All%20Duplicates%20in%20an%20Array.pdf
Thanks!!
New Vector Liya To Space Complexity O(n) Ho gyi Na....?
Which Approach Faiz ?
But question me Array return karne ke liye bola hai
@@codestorywithMIK Optimal 🎯
Actually we usually don’t consider the result data structure(which we have to return) in the space complexity.
@@codestorywithMIK Got it, Thanks 👍🏼
sort(nums.begin(), nums.end());
vector 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 😄
but sorting o(nlongn) lege, aur tujhe ques me mention kia hai o(n) and o(1) me karne ke lia, interview se nikal dege aaise karega to
remove which line, sort? nope without sorting ur code won't work@@sjxsubham...
@@kartikforwork baat to shi hai