Single Element In Sorted Array | Leetcode

In case you are thinking to buy courses, please check below:

---------------------------------------------------------------------------------------------------------------------------------------------------- Pr-Requisites: Binary Search

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

#dsa​ #striver #leetcode

[takeUforward]

Do write "understood" if you understood, motivates me :)

[SR-wevl]

This explanation might help:

Ideally, every even index should contain the first occurrence of the element and odd index should contain the second occurrence of the previous identical element. If there is an element in the array(with no duplicate) that means there will be distortion in this behavior in some part of the array. The distortion will start from the index where the single element element occurs. Use Binary search to check if the middle element follows the ideal behavior. If yes then the single element occurs to the right of the middle element. If not, it means that the single element lies to the left of the middle index. That’s how we reduce the search space.

[virajasmane]

I'm currently not doing the SDE sheet because want to complete the fundamentals first, but still I make sure to open the video and like it, just so that you get the motivation and continue doing what you're doing. Thank you for everything you're doing for the community bhai🔥🙌
PS : also hope you and your fam is safe from cyclone.

[vishanksharma]

The upload freq. is on fire 🔥 Can't thank you enough man.... May god bless you and keep going 🔥

[ghoshdipan]

Understood++!
And also I didn't knew the xor property. Many many thanks for that. Learned a new thing.😌

[prathmesh]

int nums) {
int ans =0;
for(auto i : nums){
ans = ans ^ i;
}
return ans;
}

[sanbidrc]

This "simple" observation was so elegant

[vasujain]

You're absolutely killing it and I cannot wait to watch this video for the video!

[DheerajKumar-lctx]

class Solution {
public:
int nums) {
int n = nums.size();
int low=0;
int high=n-1;

while(low <= high){
if(low == high)
return nums[low];

int mid = low + (high-low)/2;

// duplicate element not found in neighbour of start/end
if((mid==0 && nums[mid]!= nums[mid+1]) || (mid==n-1 && nums[mid]!= nums[mid-1]))
return nums[mid];

//duplicate element not found in neighbour
if(nums[mid]!=nums[mid-1] && nums[mid]!=nums[mid+1])
return nums[mid];

//duplicate element in right side
if(nums[mid]==nums[mid+1]){
if(mid%2 == 0) // even no. of elements in left of mid
low = mid+1;
else
high = mid-1;
}

//duplicate element in right side
if(nums[mid]==nums[mid-1]){
if(mid%2 == 0) // even no. of elements in left of mid
high = mid-1;
else
low = mid+1;
}

}
return 0; // return any int here
}
};


A bit lengthy, but on general pattern.

[abcmovies]

you are so great sir, your teaching skill is so good

[RamKumar-kzgg]

Very nice explanation, sir.
Thank you for the video.

[somdebsar]

Impressed by the right shift operator you have applied!! and the observation is marvellous!!!

[nightbot]

Bhi I am stuck in understanding of time and space complexity .
Can u please make a vedio on maths behind time and space complexity 🙏

[avishkargaikwad]

Can't control to thanks this man...
By applying if condition statement stuff my lines of code was 44 lines:> and with your solution it was just 7 lines😇😄..

[raunakkumar]

Taking h=n-1 also works as for the case last element is answer mid will also point to it, since its ans arr[mid]=arr[mid^1]
will not work and hence we will break out of loop.
return arr[l]

[RAHULSINGH-kqmo]

Is it necessary to store n - 2 in high??.. Can't we store n - 1 in high??Please tell me and also mention the problem which will arise if do this??

[kartikeyaagrawal]

in the upcoming question "Median of 2 sorted arrays " plz do explain the edge case arr1 [] = {97, 98}, arr2 [] = {1, 2, 3, 4}. Thank you

[ankitchetwani]

In this question, I had applied the logic same as median matrix means assigning low as 0 and high as 10^5 and I am checking for the numbers less than or equal to mid.If the count of numbers less than or equal to mid is even means single element is on right side else it is on left side.
According to me its time complexity is O(32*log(n)).
So is this logic fine in an interview?

[MultiFacebookers]

I was asked this question on Amazon on campus internship interview 2 years ago

[somdebsar]

Like if the operation if(arr[mid]==arr[mid^1]) is not true, it means that there has been disturbance before which makes it false and hence we check the left side else we check further