Single Element in a Sorted Array - Leetcode 540 - Python

hey everyone welcome back and let's write some more neat code today so today let's solve the problem single element in a sorted array we're given a sorted array of integers maybe like this one over here there will be two copies of every number in the array except for one of them and that's the one that we want to return so there's going to be two ones two threes two fours but there's a single two and that's the value that we want to return it's pretty easy but the catch here is that we want to do this in log n time and constant space are there any algorithms that you know that would satisfy this well I can think of one and it is binary search but it's not going to be as straightforward as a typical binary search but let's try to make some key observations that can get us to the optimal solution the idea behind binary search is that we have a left pointer and a right pointer and this this besides our search space initially we have no idea where that Target element could be so we have to search the entire array but we'd like to be able to eliminate half of the array every iteration of like our Loop so maybe we would look at this element is this the target element well how do we know if 3 is the target element or not well because our array is sorted conveniently for us it's really easy in constant time we can look at any element and determine whether it's the Target or not that's by looking at the left neighbor and looking at the right neighbor because we know for the Target element when we look at the left neighbor it's going to be different than the target element and when we look at the right neighbor it's going to be different than the target element but for every other element in the array that's not the case for three but both of its neighbors are not different than it for this three both of its neighbors are not different than it for this for both of its neighbors are not different than it so that's easy enough we initialize our mid pointer here we look at the three or both of its neighbors equal to it nope so this is not the answer but how do we know now should we start searching over here or should we start searching over here at first it seems it's impossible for us to know which side to go to but actually there's a clever observation we can make first of all we didn't just eliminate this value there are two copies of it so we also eliminated the second value now it might look a little more obvious and if it's still not obvious which side we should search on let me tell you something if we're given two copies of every single value then let's say the size of our array is 2 times n but we know in addition to the even values there's going to be a single one where there's just a single instance of it so an odd number of times this value will be added or just one time so this is the size of our array it's always going to be odd so which side should we search on you can probably tell me at this point but it's always going to be the side that has an odd number of values so if this side has three values and this side has two values well we know this side is going to contain only duplicates because it's even but we know this side is going to contain the odd value or rather the unique value so that's how we would decide it so continuing our algorithm here I'm going to set the mid pointer over here and let's also eliminate these values from our search space as well so now I'm going to eliminate these values from our search space our mid pointer was over here but now we're going to take our right pointer and shift it over to Mid minus one so it's going to go over here and then we're going to continue the algorithm so the mid pointer now is going to be over here is this the target value well it's not different than both of its neighbors so no it's not and its left neighbor is equal to it so that's also not a part of the search space so now we would set our left pointer to be mid plus 1 over here so if our left pointer is over here now we would look at this guy is it different than its left neighbor yes it's different than its right neighbor yes it's the answer and that's what we're going to return and as you can see this is just a modified binary search so this time complexity is going to be log n and the space complexity we're not using any additional data structures is going to be Big O of n now let's code it up so let's start with initializing our left and right pointers the left pointer is going to be at the beginning of the array while the right pointer is going to to be at the end of the array and we're going to keep going while our left pointer has not crossed our right pointer and then the first thing we want to do is compute the Midway point so you can either do left plus right divided by 2 with integer division but believe it or not this actually is a bug most people don't know it and usually it doesn't matter for interviews but the bug is that left plus right can overflow so how can we get the Midway point between the left and right pointers without possibly having these two added together overflowing well to do that we take the difference between write minus left so this gives us kind of half of the size of our search space and we take this value and we add it to the left pointer alternatively we could also subtract it from the right pointer but basically this just says get the left pointer add half of the size of this subarray to the left pointer and that will give us an a Midway Point since we're subtracting these there's no risk that it's going to overflow that's just a minor point about binary search but now let's continue let's first determine if we found our answer or not so how do we do that well we can say if the number at Mid minus 1 is different from the value at the mid index and if the value at the mid index is different from the value on the right side of it then we know we found our answer because it's different than both of its neighbors so we return that mid value one little bug though with this is that what if our index gets out of bounds well for that we can modify this slightly and say before checking this let's check that mid minus one is greater than zero that's one thing we could do but I'm actually going to do the opposite if mid minus 1 is less than zero or if this whole thing this part is true then we know it's not equal to its left neighbor that's what we're trying to determine here so if mid minus 1 is out of bounds then of course it's not equal to its left neighbor because it doesn't have a left neighbor and we'll do the same thing over here with the right side if the mid plus 1 is equal to the length of the input array or this is true or it's equal to its right neighbor then we're good so either it doesn't have a right neighbor or it's equal to its right neighbor in that case we know we found our answer so we return it and the benefit of this is that it'll always evaluate the left side first so if mid minus 1 is less than zero it won't even evaluate this side because there's an or in between these if this is true it won't even check the second one because it knows this whole thing will be true but pay attention to how we have the parentheses because it does matter in this case we need this entire thing and this entire thing to be true so now if that's not the case we need to figure out which side of the array has an odd number of values so the easiest thing in my opinion is to just get the size of the left side of the array because we really only need one side of the array if it's odd then we'll search it if it's not then we'll search the other side but how do we get the size well the left side of the array is going to be M minus one if the value at M minus 1 is equal to nums at index M otherwise it's going to be M this is because if these two values are equal then we want the number of values on then we want the number of values to the left left of M minus 1. if M minus 1 is 3 for example like it's index three how many values are on the left side of three well the indexes of those values are going to be 0 1 and 2. so there's three values on the left side of the index three so that's how we're getting this and if that's not the case that means that the value at index m is equal to the value at M plus one because we know it's equal to one of its neighbors and in that case we would want all the values to the left of M which is just going to be M so one thing I want to mention here is that what if M minus 1 is out of bounds well in Python that would be negative one zero minus one is going to be negative 1 and python negative one actually does work it will though just look at the last value in the array which will be different for sure because our array is sorted but in most languages you might need to have another check here I'm just mentioning that for the people who don't use Python but using this left size we can and say if the left size modded by 2 evaluates a true meaning there's an odd number of values on the left side then we say right pointer is going to be M minus 1 because now we want to search the left side otherwise we are going to say left pointer is equal to Mid plus 1 because we want to search the right side that's the entire code we don't have to put any return statements out here because we are guaranteed that there's a solution and if there is we're going to return it right over here so now let's run the code to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neatcode.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon