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.co...

[@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

[@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.

[@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 :)

[@aniruddhabhattacharya807]

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

[@techdose4u]

Thanks for sharing

[@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

[@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.

[@ajaygonepuri2285]

Great Explanation better than anyone on TH-cam!!

[@techdose4u]

:)

[@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

[@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.

[@saraswatirathore3933]

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

[@techdose4u]

Welcome 😊

[@yitingg7942]

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

[@techdose4u]

Thanks :) You are not replying now 🥺

[@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.

[@oqant0424]

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

[@techdose4u]

:)

[@gautamtyagi8846]

thanks a lot, very easy to grasp ur explanation

[@punittripathi5461]

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

[@techdose4u]

Okay sure

[@captain_vegan]

Very helpfull thank you, u deserve million subs, man

[@SirAkPandey]

Best explanation for this problem

[@shivatomar4319]

Bhetreen samjhaya Bhai 👏🏼🙆🏻‍♂️

[@techdose4u]

Dhanyawaad bhai :)

[@vivek.tiwary]

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

[@Harish-ll9tv]

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

[@adityajain3664]

NIce intuitive solution.

[@prathaps2753]

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

[@techdose4u]

Welcome :)

[@rahulbhalla9891]

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

[@letsdoeverythinginoneweek9398]

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

[@techdose4u]

👍🏼

[@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.

[@cristianouzumaki2455]

Your explanations are gems. Thanks sir.

[@MJ-zs5jv]

Such a great explanation!

[@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

[@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.

[@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.

[@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

[@ashwinvarma9349]

Thats awesome man! Keep up the good work!

[@techdose4u]

Thanks

[@uv9111]

Amazingly explained

[@anurag_ad_01]

great solution

[@gokulnaathbaskar9808]

Thank you so much!
Loved the pair index property

[@chandrukumar8131]

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

[@chandrukumar8131]

see this solution sir

[@techdose4u]

This is O(N).

[@saranshkumar4777]

Simplest Approach :)

[@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

[@mohammedyunusshaikh5080]

Thankyou Sir for the great explanation

[@ambarishrishu]

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

[@priyanshukhullar5836]

Awesome dada

[@techdose4u]

Thanks :)

[@krishnavamsinadharikatla5150]

Good approach 👏👏

[@techdose4u]

Thanks :)

[@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.

[@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.

[@newBieGuy05]

awesome explanation bro

[@GhostRider....]

Nice explanation sir 🔥🔥

[@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

[@TarunSharma-iv7iv]

Great Explanation!!

[@techdose4u]

Thanks :)

[@guptasaurabh688]

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

[@techdose4u]

Wacom pro

[@nayankhuman1043]

Love your explanation ❤

[@nikhillingam4630]

I'm waiting Hurrah!

[@techdose4u]

:)

[@apoorvraizada]

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

[@techdose4u]

Welcome :)

[@tejailla7431]

This will works when duplicate elements exits in pairs

[@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 :)

[@santoshbhupati3579]

Thanks

[@techdose4u]

Welcome :)

[@AjaySingh-ll5qw]

Nice..

[@techdose4u]

Thanks :)

[@agileprogramming7463]

Awesome as always!!

[@techdose4u]

Thanks :)

[@spetsnaz_2]

Nice explanation!

[@techdose4u]

Thanks :)

[@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👍👍

[@sourabhajoshi2129]

Thank you

[@SmokyBigSmoke]

Thank you so much.

[@techdose4u]

Welcome

[@sarthakchoudhary811]

amazing sir.

[@techdose4u]

Thanks :)

[@ashutoshshukla650]

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

[@techdose4u]

Yes you can use this or bitwise & as well.

[@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

[@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

[@_ankush_verma]

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

[@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

[@yaswanthp2294]

Is it allowed to have same element more than two

[@apoorvbagal2936]

No

[@aniketbasu3865]

bro you are awesome :)

[@techdose4u]

Thanks 😊

[@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

[@punjabicodingstyle5111]

Amazing

[@techdose4u]

Thanks :)

[@dhanashreegodase4445]

Thankuuuuu

[@techdose4u]

Welcome 😀

[@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

[@nick-sx2zn]

what if there are theree 1s on left side

[@yaswanthp2294]

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

[@gauravmishra8782]

Hey anyone what is purpose of checking the boundary element

[@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

[@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.

[@navinchainani4721]

We can use xor its too easy

[@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

[@kushgupta1187]

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

[@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

[@sayanmaitra11]

thanks