Find all Duplicates in an Array (LeetCode 442) | Full solution with no Extra Space

To see more videos like this, you can buy me a coffee: www.buymeacoffee.com/studyalg...
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

[@abhi121able]

Superb Work. Explanation is too good. Very smooth :)

[@ranchodas]

Very well explained bro !!

[@shraddhajain8935]

Really helpful. Thanks

[@gauravmasalkar3546]

great work keep it doing

[@deliveringIdeas]

Thank you tremendously

[@deepeshreddy4700]

Please don't stop uploading videos it is helping a lot for students like me

[@nikoo28]

Sure...do help me out by sharing this video as much as you can :)

[@deepeshreddy4700]

@@nikoo28 Okay

[@rishidangi2978]

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!!

[@nikoo28]

What was the programming contest you are referring to?

[@user-mx9kp8js8v]

great explanation

[@NikhilVerma-kk6xc]

bhaisahab mst explaination

[@pratikpatrimath4887]

superb 😎😎😎

[@shivaniverma4266]

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

[@nikoo28]

thank you so much for these kind and awesome words

[@rajkumarp9943]

Good 💥

[@utkarshjoshi2915]

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 ?

[@PRASANTH-if9se]

why answer is repeating when they occur in the array more than 4 times

[@chinmayjain9705]

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]

[@AmitChauhan-sp1cw]

how to implement code for returning -1 when repeating element does not exist?

[@nikoo28]

That will be a very small change in the code. If the resultSet is empty at the end, you can return a “-1”

[@manishkumar-xc2zp]

why we have (index+1) , can anyone explain

[@nikoo28]

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.

[@choudharyhimanshu4134]

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.

[@ujjawalsharma1120]

Overall TC will be O(nlogn) here.

[@sreddy8141]

Bhai, wanna know about desktop space analysis problem

[@nikoo28]

I can’t find the link to the problem. Reach out to me on my email available in channel information.

[@prabaljana9714]

If the element encounted 0 the. What to do

[@nikoo28]

Then you will have to handle the 0 differently. For this particular problem check the constraints: 1

[@chinmayjain9705]

👍

[@hemav9981]

If the element is 0 ,index becomes -1. It is showing array index out of bound error. How to solve this issue?

[@vrishtiupadhyay5028]

Element will never be 0 as we have range from [1,n]

[@vanshbhatnagar1117]

class Solution { public: vector findDuplicates(vector& nums) { vector result ; for(int i=0; i

[@AkashRK07]

Doesn't creating a result set consider as extra space?

[@nikoo28]

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.

[@AkashRK07]

@@nikoo28 understood 🙌🏻

[@nikhilbansal3731]

What is name of the approach

[@nikoo28]

I don't know if there is a specific name to this approach

[@user-oz2eu7rs8v]

don't you think you are using o(n) space by modifying the array itself

[@unemployedcse3514]

space remains constant since , seperate or extra space is not utilised

[@suryav8458]

Please some times name the Alogrithm name also otherwise everything is good

[@nikoo28]

not every algorithm has a name, and your interviewer will never ask the algorithm name.

[@ujjawalsharma1120]

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.

[@nikoo28]

What do you mean by not giving a sorted array? You are looking for duplicates..right??