Single element in a sorted array | Leetcode

This video explains a very important programming interview question which is to find the unique element in a sorted array in just O(logN) time and O(1) extra space. This problem would have been extremely easy to solve provided we were allowed O(N) time. This can be solved by simple linear search or XOR operation. In order to take benefit of sorted array property, we can use binary search algorithm with some observations to find the unique element in just O(logN). I have shown 4 observations and used them to solve the problem in O(logN) time using binary search algorithm.At the end of the video, i have explained the CODE. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...

[@NeverGiveUp186]

Easy approach to toughest of the questions...This man is simply a legend !! 🙌🙌

[@techdose4u]

😅

[@shreyasvishwakarma8979]

Shocked to see that you have around 90k subscribers . You deserve atleast 500k subscribers dude !

[@techdose4u]

😊 Thanks

[@angrybutterflys]

You are the best channel for these solution videos! Your explanations are so clear and are very helpful for me during the job search!!!

[@techdose4u]

Thanks :)

[@TechBroQuiz]

Finally understood this question after seeing four different videos.Thanks a lot🙏

[@ankushreddy9789]

oh yeah... this is easily the most intuitive of all the other videos for this question.

[@wasimahmad9927]

Amazing, i saw a lots of video but i did not clear the concept but you are amazing and you know how to teachs

[@gokulnaathbaskar9808]

Thank you so much! Loved the pair index property

[@cristianouzumaki2455]

Your explanations are gems. Thanks sir.

[@yitingg7942]

Thanks a lot Surya! Couldn't think of this approach myself.

[@techdose4u]

Thanks :) You are not replying now 🥺

[@satyamgupta6030]

very nice and different solution thanks alot I was very confused how will we change the left and right values but this video helped me clear my doubts.

[@MJ-zs5jv]

Such a great explanation!

[@uv9111]

Amazingly explained

[@nayankhuman1043]

Love your explanation ❤

[@gautamtyagi8846]

thanks a lot, very easy to grasp ur explanation

[@rahulbhalla9891]

Please upload more and more videos. Your video is very helpful

[@captain_vegan]

Very helpfull thank you, u deserve million subs, man

[@saraswatirathore3933]

Wonderful explanation ,and I am thankful for your efforts which help me to understand the concept.

[@techdose4u]

Welcome 😊

[@vivek.tiwary]

As usual, great explanation !!. Do you have any playlist for binary search?

[@ashwinvarma9349]

Thats awesome man! Keep up the good work!

[@techdose4u]

Thanks

[@ajaygonepuri2285]

Great Explanation better than anyone on KZbin!!

[@techdose4u]

:)

[@SirAkPandey]

Best explanation for this problem

[@prathaps2753]

you are superb man!! keep making videos . Your channel helps a lot

[@techdose4u]

Welcome :)

[@anurag_ad_01]

great solution

[@adityajain3664]

NIce intuitive solution.

[@mohammedyunusshaikh5080]

Thankyou Sir for the great explanation

[@GhostRider....]

Nice explanation sir 🔥🔥

[@MohitKumar-zh9en]

awesome explanation bro

[@agileprogramming7463]

Awesome as always!!

[@techdose4u]

Thanks :)

[@oqant0424]

u explained it so well........ u r simply a legend !! 🙌🙌

[@techdose4u]

:)

[@TarunSharma-iv7iv]

Great Explanation!!

[@techdose4u]

Thanks :)

[@sourabhajoshi2129]

Thank you

[@spetsnaz_2]

Nice explanation!

[@techdose4u]

Thanks :)

[@shivatomar4319]

Bhetreen samjhaya Bhai 👏🏼🙆🏻‍♂️

[@techdose4u]

Dhanyawaad bhai :)

[@krishnavamsinadharikatla5150]

Good approach 👏👏

[@techdose4u]

Thanks :)

[@sayanmaitra11]

thanks

[@letsdoeverythinginoneweek9398]

nice bro why i like u because my approach && my thinking ==your approach + your explanation

[@techdose4u]

👍🏼

[@apoorvraizada]

The best explanation, Thank you so much for making great content.

[@techdose4u]

Welcome :)

[@marvellouschandan]

No words, really Hats off to you brother... :D

[@techdose4u]

Thanks :)

[@marvellouschandan]

@@techdose4u Hey brother, could you please help me out, I am not able to understand the "Median of two sorted arrays of different sizes", please help me out with this question, youtube doesn't have a good explanation of this question.

[@techdose4u]

I will soon make a video on that :)

[@marvellouschandan]

@@techdose4u Thank you :D

[@priyanshukhullar5836]

Awesome dada

[@techdose4u]

Thanks :)

[@shivarammuthukumaraswamy7164]

Thank you so much.

[@techdose4u]

Welcome

[@ambarishrishu]

nice video keep it up. do the solution in python. most people like me uses the python.

[@Harish-ll9tv]

Sir ,i done this problem like this int singleNonDuplicate(vector& nums) { int ans=0; for(int i=0;i

[@ArpitDhamija]

can you make some videos on hard graph,DP and trees problems. Please make some videos on binary lifting, euler tour , etc and their questions. I have just listened their names and don't have idea that what are they, and its confusing to studying codes, your videos are helpful for that purpose. Please make some videos on these topics and cover some hard questions which are asked in interviews

[@techdose4u]

Yea I am on my way. Problem is, I don't have my GPU now and so rendering is very difficult and time taking. I am still trying to cover all topics of graph.

[@ArpitDhamija]

@@techdose4u thanx

[@agammishra9674]

great Explanation!!! thanks, but do we need to check that odd even index to decide which partition to check, what if we do normal BS, like if x>mid then low=mid+1 elif x

[@agammishra9674]

Please do reply, I think I am missing something

[@techdose4u]

This will not work. To decide which subarray to search, you need to check index.

[@mukulupadhyay4656]

how would you find that X you are searching for that only, you are not given the target in this question unlike normal binary search.

[@AjaySingh-ll5qw]

Nice..

[@techdose4u]

Thanks :)

[@varunoyal87]

TechDose: I have one query , after seen the logic Its very easy to understand the approach .But could you please help me how should I build my own logic or approach to solve the any problems of programming. Thanks

[@ahmedjubayer5419]

practice and practice. there is not alternative.

[@sarthakchoudhary811]

amazing sir.

[@techdose4u]

Thanks :)

[@punjabicodingstyle5111]

Amazing

[@techdose4u]

Thanks :)

[@santoshbhupati3579]

Thanks

[@techdose4u]

Welcome :)

[@aniruddhabhattacharya807]

class Solution { public: int singleNonDuplicate(vector& nums) { int n = nums[0]; for(int i=1;i

[@techdose4u]

Thanks for sharing

[@nikhillingam4630]

I'm waiting Hurrah!

[@techdose4u]

:)

[@aniketbasu3865]

bro you are awesome :)

[@techdose4u]

Thanks 😊

[@punittripathi5461]

Can u please increase the size of code in your upcoming videos. Appreciate , what u are doing.

[@techdose4u]

Okay sure

[@madhavsahi7400]

Sir what if the question was that the elements can occur more than 2 times except for the unique element then will this approach work ??...or what will be the right way to solve that question other than using O(N) time

[@techdose4u]

Array should have special property to capitalise on. Otherwise, there won't be a way less than O(N).

[@madhavsahi7400]

@@techdose4u okay sir thanks

[@dhanashreegodase4445]

Thankuuuuu

[@techdose4u]

Welcome 😀

[@tejailla7431]

This will works when duplicate elements exits in pairs

[@syed7996]

how you came up with this partition property and pair index property? (how you got that intuition). Please explain

[@techdose4u]

By seeing the question I knew we had to use binary search. Now the question was how to use it. We could have used it using array values. So the 2nd obvious thing was index and yes it worked. That's how.

[@syed7996]

@@techdose4u stay the same man! you actually need not reply but every time I ask you, I am getting a reply! Thank You. Please post more about the intuition and various concepts involved in computer science to land a Software Engineer job

[@techdose4u]

Yea sure.

[@saranshkumar4777]

Simplest Approach :)

[@guptasaurabh688]

Which tool you are using with this pen to explain? Pls reply

[@techdose4u]

Wacom pro

[@punjabicodingstyle5111]

Can you tell about what is ios-basesync and also after this line cin.tie?

[@techdose4u]

This is for fast io in c++ by optimizing io streams. Read about it on internet.

[@NikhilKumar-oy7mx]

Have you seen the best submission? It is the xor one taking 0ms but how as it's O(n) while binary will take log n. Please reply.

[@NikhilKumar-oy7mx]

I was waiting for your video to ask question 😉

[@techdose4u]

It was because of low and weak tests cases. Also, he optimized every possible stream for max IO. He wrote it separately. You can see it.

[@NikhilKumar-oy7mx]

@@techdose4u how does max IO work

[@techdose4u]

By Max io I meant max io speed.

[@BarkaDog]

Don't look at those stupid stats. They mean nothing. If you submit multiple times you will see you get different times. Just make sure you have the best time complexity and you are good to go.

[@anmolsharma9539]

public int singleNonDuplicate(int[] nums) { int l = 0, h = nums.length - 1, mid; while(l < h) { mid = l + (h - l)/2; if(mid%2 == 1) mid--; if(nums[mid] == nums[mid+1]) l = mid + 2; else h = mid; } return nums[l]; } how about this one

[@codeminatiinterviewcode6459]

Sir i am in a confusion of using low=mid+1, high = mid ; and taking while(low

[@techdose4u]

That's a good question. Actually it depends on your formula being used. The best formula for mid is low+(high-low)/2. For this, we generally use low

[@sunnyjain2444]

@@techdose4u What I think is , if you use while(low

[@nick-sx2zn]

what if there are theree 1s on left side

[@gauravmishra8782]

Hey anyone what is purpose of checking the boundary element

[@_ankush_verma]

I doubt that it won't work in case when some elements are triplets then pair property will not help[

[@nagajaswanth831]

did it in python: class Solution(object): def singleNonDuplicate(self, nums): n=len(nums) low=0 high=n-1 while low=1 and mid

[@techgamer1333]

Why we don't use Counting Algorithm ?? If the Count==1 return True? Is this Take More Time I guess O(N+K)? BST gave us Optimal Solution Log(N) ?? Is it?

[@techdose4u]

Nope. It will take O(N) because you need to visit all elements to count them.

[@v.sreesairam9488]

bhaiya is it ok to do mid=(low+high)/2 inside the binary search

[@techdose4u]

It depends. Just do a dry run and check.

[@v.sreesairam9488]

Ok bhaiya thanks for your reply

[@krishnakantahirwar6418]

It sometime gives you stack overflow otherwise it's okk👍👍

[@yaswanthp2294]

Is it allowed to have same element more than two

[@apoorvbagal2936]

No

[@ashutoshshukla650]

if (nums[mid] == nums[mid ^ 1]) can handle even and odd

[@techdose4u]

Yes you can use this or bitwise & as well.

[@chandrukumar8131]

return sum(set(nums))*2-sum(nums)

[@chandrukumar8131]

see this solution sir

[@techdose4u]

This is O(N).

[@PersistentProgrammer]

Python Version: class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: """ :type nums: List[int] :rtype: int """ left = 0 right = len(nums) - 1 #Edge case if right == 0 or nums[0] != nums[1]: return nums[0] if nums[right] != nums[right-1]: return nums[right] while left

[@sonuagarwal7679]

Will it matter that array is sorted or not ? I don't think so.

[@techdose4u]

The pair property won't work. This technique is very specific.

[@sonuagarwal7679]

So basically sorting is bringing same number together. Thanks

[@sahildigikar9115]

Hey, can you please tell me which problems to solve in graph and dp, you have earlier said 10 problems of dp in our video. But still can you please tell me so that I can cover all the patterns of dp. The graph and dp concept is slightly hard.

[@techdose4u]

Try to cover all top 20 questions from all ropics on geeksforgeeks. This should get you going.

[@sahildigikar9115]

@@techdose4u Okay thank you

[@techdose4u]

Welcome :)

[@yaswanthp2294]

It only works when each element exactly appears twice, but one element appears exactly once Please clarify that

[@engineervinay]

alternate code: int singleNonDuplicate(vector& nums) { int low=0,high=nums.size()-1; if(high==0){ return nums[0]; } while(low

[@engineervinay]

where we don't need to check for the adjacent element which may give the array index out of bound error. C++ leetcode all testcase passed.

[@navinchainani4721]

We can use xor its too easy

[@oladimejijames9554]

Hello sir, i did it like this and passed all the test cases, can you help improve this solution: if(numbers.length==1) return numbers[0]; int current = 0; final int nonRepeated = 0; Map mp = new HashMap(); for (int i = 0; i

[@navinchainani4721]

We can solve by using xor also

[@retrogame3138]

I used map and then check occurrence if it is one i return it Is it right approach And time complexity?

[@vishnuvardhan-wq5qi]

I think its O(n)

[@techdose4u]

It is not a good technique. Question asked to solve in LogN due to special property of array.

[@techdose4u]

Yes you are right.

[@BarkaDog]

It is O(n) time and o(n) space. The question says to do in logn time and constant space

[@GauravKumar-wm4cm]

@@techdose4u we could have used xor or array ans we will get the ans 2 line code

[@swapnilsah3680]

what if there are 3(three 1 1 1 2 2 3 4 4 ) 1's at the starting

[@techdose4u]

There cannot be....because this doesn't follow the question constraints. Please read the question carefully.

[@niranjanhegde1535]

So how pair index proper holds in this case. Start at even index and end at odd index [1,1,1,2,3,3]?

[@ianpan0102]

Every element appears exactly twice, except for one element which appears exactly once

[@techdose4u]

Your input is wrong. It doesn't comply with question.

[@vishnuvardhan-wq5qi]

@@techdose4u so the input must be like all the other numbers except the unique number should follow same pattern .. am i correct??

[@niranjanhegde1535]

@@ianpan0102 ohh. Correct. Thanks

[@hoperadas6010]

class Solution { public int singleNonDuplicate(int[] nums) { int low = 0; int high = nums.length - 1; if(high==0) return nums[0]; else if(nums[0]!=nums[1]) return nums[0]; else if(nums[high]!=nums[high-1]) return nums[high]; while(low

[@kidoo1567]

U dint explian code

[@piltonswrangbrahma5140]

int singleNonDuplicate(vector& nums) { int lo = 0, hi = nums.size() - 1; if (hi == 0) return nums[0]; else if (nums[0] != nums[1]) return nums[0]; else if (nums[hi] != nums[hi - 1]) return nums[hi]; while (lo

[@kushgupta1187]

public int singleNonDuplicate(int[] nums) { int low=0; int high=nums.length-1; int mid=0; while(low