Find all Duplicates in an Array (LeetCode 442) | Full solution with no Extra Space
VloĆŸit
- Äas pĆidĂĄn 26. 07. 2024
- You are given an array of integers that have some values that appear twice and others appear once. Return a list of all the duplicate elements. Watch this video to learn 3 methods of solving this question. A Brute Force method, using a Hash-set with extra space and a trick to where you do not need any extra space. The biggest hint is that all the elements of the array are greater than equal to 1 and less than equal to the length of the array. Learn with great animations and visuals of what happens behind the scenes.
00:00 - Intro
01:19 - Problem Statement and description
03:24 - Method 1: Using HashSet
06:07 - Method 2: Without Extra Space
12:25 - Dry-run of Code
14:53 - Final Thoughts
đ Links to topics I talk about in the video:
Brute Force Algorithm: âą Brute Force algorithms...
Time Complexity of an Algorithm: âą What is the Time Compl...
Actual problem on LeetCode: leetcode.com/problems/find-al...
đ A text based explanation is available at: studyalgorithms.com/array/lee...
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
đ Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to learn algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
đ To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
đ„ My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
đ» Get Social đ»
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview
Superb Work. Explanation is too good. Very smooth :)
Very well explained bro !!
great work keep it doing
Really helpful. Thanks
Please don't stop uploading videos it is helping a lot for students like me
Sure...do help me out by sharing this video as much as you can :)
@@nikoo28 Okay
Thank you tremendously
this one and yesterday's problem where we assumed our array to be a linked list and tried to find the node where the loop starts (Leetcode 287: find the duplicate number) were kinda hard to think when solving for the first time.
One thing I can surely note from this that if the value of integers is always less than the length of the array (or one less), we can use it as an index to the array.
Thanks for the explanation!!
What was the programming contest you are referring to?
great explanation
bhaisahab mst explaination
you are genus you are amazing you just smoothly put that logic in hour mind that in my dreams i can scream it lout all i am saying is whaattttttta content , you have such a great skills keeep doing , i am greatful for this channel
thank you so much for these kind and awesome words
superb đđđ
Good đ„
Example taken in method 2, what if second occurrence of 3 is before 2(i.e, 2 and 3 change their positions of second occurrence, 2 at index 6 and 3 at index 5), at that situation , answer will not be in ascending order. Then we have to sort the returning array again ?
why answer is repeating when they occur in the array more than 4 times
Heap sort can be use with space comp O(n).
If 0(1)
Arr[arr[i]%n ] = +n
New arr[I]
Again we will bring back original array by
Arr[I]
how to implement code for returning -1 when repeating element does not exist?
That will be a very small change in the code. If the resultSet is empty at the end, you can return a â-1â
Can't we first sort the array and then iterate over the array and look for duplicates by comparing adjacent elements. Sorting will take O(nlogn) time and iteration will take O(n) time and no extra space is required. So, overall TC is O(n).
Do correct me if I am wrong.
Overall TC will be O(nlogn) here.
why we have (index+1) , can anyone explain
That is because the index ranges from 0 to (n-1)
But the array elements are from 1 to n
So if you do (index + 1) you are referring to the actual elements present in the array.
đ
Bhai, wanna know about desktop space analysis problem
I canât find the link to the problem. Reach out to me on my email available in channel information.
class Solution {
public:
vector findDuplicates(vector& nums) {
vector result ;
for(int i=0; i
don't you think you are using o(n) space by modifying the array itself
space remains constant since , seperate or extra space is not utilised
If the element is 0 ,index becomes -1. It is showing array index out of bound error. How to solve this issue?
Element will never be 0 as we have range from [1,n]
If the element encounted 0 the. What to do
Then you will have to handle the 0 differently. For this particular problem check the constraints: 1
Doesn't creating a result set consider as extra space?
You are expected to return a result set, no need to count that.
When we talk about space complexity, usually it is the extra space you would be needing.
@@nikoo28 understood đđ»
Please some times name the Alogrithm name also
otherwise everything is good
not every algorithm has a name, and your interviewer will never ask the algorithm name.
What is name of the approach
I don't know if there is a specific name to this approach
it will not give sorted array for this input n = 8,
4 3 2 4 8 2 3 1, how to fix it, pls correct me if input is not valid.
What do you mean by not giving a sorted array? You are looking for duplicates..right??