Find duplicate in an array of N+1 integers |Q11| Love Babbar DSA sheet
Vložit
- čas přidán 2. 11. 2020
- #coding #competitiveprogramming #interviewquestions #dsaseries
In this video I have explained the 11th problem.
Time Complexity = O(N)
Space Complexity = O(1)
Love Babbar DSA sheet : drive.google.com/file/d/1FMdN...
Hope you like it. If have any doubt then just comment down below.
LIKE | SHARE | SUBSCRIBE
The problem states we have to solve it without modifying the array
I have one doubt that it's time complexity will be o(n^2)
So it will not applicable
Instead that we will use brute force approach (linear search)??
If any one agree to my doubt plz like and if any one has solution to my doubt them plz reply
you explain in very good way
common mistake: you will take "N" which is less than the array's greatest element.
So take elements which is less than the size of the array.
Read ques carefully:
Given an array of integers arr containing n + 1 integers where each integer is in the range
[1, n] inclusive.
Osm 👍👍
Nicely explained 👍
🔥🔥
what if we have values in the array greater than the len of array
Very good 👍👍
Dry run is not understand please explain .i am not understand in dry run concept the array is when adding with the size
awesome
❤️❤️❤️❤️
Thank You very much bhai
8/6 is greater than 1
he taking array of integer type so only integer part will be saved that is 1
right it won't be greater than 1
If the element is 0 ..then what to do .. because if divided then get 0 also
Bro I am trying this question in python form past 1 hour but I am stucked can I get help from you
You Speak in striver tone
leetscode says without modifying the array but have modified it
Very well explained bro. Your way of explaining is superb . Keep it up
abe bsdk isme kya superb tha. isne toh array ko alter kiya jab ki question me array read only tha.
Thank you!
You're welcome!
🙏
But why you’re diving by array by n why the a[i]/n > 1
array modification isnt allowed
what is this ? The question was not to alter the array or It was read only......
hey man can you explain the bucketing apporach
have you made any playlist for solution of love babbar dsa sheet ?
yes you can check it out
What is the return statement in the answer in gfg?
Hiiiiii😂😂
vector return karna hai
@@ramkrushnamadole874 are Thank you sir🙂👍🏻
@@ADITYAGAIKWAD 😂
so 8/6 is greater than 1 so what does that mean ? does it mean 1 is repeated or what ?
Exactly
taking it as int will return only integer part ,so on dividing we will get 1
Explain Clearly bro
What if some elements of array is greater than size of array?
This code won't work, right?
In question, it was mentioned that all the values will be between 0 to n so here we can use the array as a hashmap as I mentioned in video but if the values are greater than n then we cannot use array as a hashmap
@@CodeLibrary got it bro, thanks!
@@CodeLibrary problem states that need to be solved without modifying the array
bro but in the leetcode problem we are assuming only one duplicate is there. But in the video there are two duplicates for three.
Even i assumed that there would be only one duplicate, so i submitted the solution for that, but there were testcases in which numbers are repeated more than twice.
I think they told about a particular number not the no of times it gets repeated , so only 1 number in the array gets repeated and it can repeat any times
bhaiya concept to samaj aa gya kese hua, but vo % wali line samaj nhi ai kya ho raha hai vaha
Should not you consider elements can be close to 10^5
Bro but we can do this problem by using for loop also
Void duplicate (int a[ ], int n){
Sort(a, a+n);
for(int i=0; i
Sorting takes longer than expected O(n) so your code may timeout
@@hanseldsilva2393 TQ
Time complexity wiil be O(nlogn)
8/6 is greater than 1 😂
Me bhi wahi bol raha tha 😂
O 8/6 ko int leta so uska ans 1 ata which is not greater than 1
bro cant we just sort the array and then check for arr[i]==arr[i+1]?
Complexity of sorting is O(n logn) which is above the expected O(n)
Beta brute force karte reh jaaoge zindagi mein
@@ishankbansal9239 to bhai sidha best se hi krna start krte ho kya sir ap fr to apko utube khol lna chiye.
@@lokeshnegi5051 mene bhi aisa hi kia tha
in making o(1) space you made ,time o(n^3)
It's O(n) only. That for loops are not nested.
bhai kaisa samjha rha hai? neend mein ho kya?
"15/6 is greater than 2".. kaise? 15/6 is 2
Try with input 1,3,3,4,5 , It will return a wrong answer
This is incorrect input.... the array size is n+1 and can have values only till n. In your case, the size is 5 and I see a 5 in it.
Array modify ho rha bhai..bina array ko modify kro wo solution dhoondh rha tha
If you don't want to modify array then use a separate hashmap for frequency of array elements, then space complexity will become O(N)....so to reduce the space complexity to O(1) I am using array as a hashmap
But still u r modifying na. Dont wnt extraa space n also dont wnt to modify ths array.. i mean i ws looking for tht explanation man...using floyd cycle detection.no modification, no extraa space , no hash map, no hash table , no set ...like tht.understood bro? Link list kind of approach...internally doun everythn.
class Solution {
public int findDuplicate(int[] nums){
int[] a=new int[nums.length];
for(int i=0;i
Sasta Love Babbar..😄
bro array must not be modified
May the worst one
bhai time complexity name ki bhi cheez h dekh to le question me duniya bhr ke loop ni chalane ek me krna h
are kehna kya chahte ho 😑
Not effective solution...
at least read the question b4 making a vedio
Bakwaas
Bad explanation , didn't understand anything...
You don't make right choice of vocabulary when speaking English. So a lot of times your sentences don't explain what what you're actually thinking in that moment. That wastes a lot of time just trying to understand the approach and your code.
The solution: Just speak in Hindi. At least your choice of words would explain the thing accurately there. For English viewers, you can add subtitles.