Microsoft Coding Interview Question - Single Element in Sorted Array (LeetCode)

[@MingoDynasty]

I think most people would be afraid to jump +2 or -2 from mid like that, in case of going outside the bounds of the array. Going through two example test cases with array lengths 1 and 3 would be a good idea to show that this is actually always safe.

[@vedantshinde2277]

Yes! You nailed the intuition...we essentially need to see if the subarray is "really" odd.

[@AlgosWithMichael]

Yep exactly!

[@mananvarma5944]

This was a great intuitive solution, thanks!

[@AlgosWithMichael]

Glad it was helpful!

[@rkk1990]

How do one remember such techniques during the interview ?

[@devkunjadia3792]

I love your content. Keep up the great work!

[@bimerinoel4913]

that's very cool. i got something simple also, check this: public static int singleElement(int[] arr) { if (arr.length == 0) return 0; for (int i = 0; i < arr.length; i++){ if (i == arr.length-1) return arr[arr.length-1]; if (arr[i] == arr[i+1]) i++; else return arr[i]; } return 0; }

[@surbhiagarwal2322]

Good solution. I thought of the same at first, but worst case is O(n) --> element at the last.

[@TheRomanianWolf]

@@surbhiagarwal2322 O(N), both solutions will be rejected.

[@haoooyuliu6857]

nice explanation, really help for this question!

[@AlgosWithMichael]

Glad it helped you, thank you for watching!

[@jamesyoo67]

FYI I don't think this works when the last element is the unique number

[@vasumahalingam5162]

Ifs should check the boundaries; mid-1 >= 0 and nums[mid] == nums[mid-1] and mid + 1 < len(nums) and nums[mid] == nums[mid+1]

[@AlgosWithMichael]

I verified the solution works with the following input: [1,1,2,2,3,3,4,4,8]. The reason why it works is because the if checks check mid - 1 and mid + 1. This problem is pretty tricky because of all the edge cases haha. Thanks for watching!

[@AlgosWithMichael]

@@vasumahalingam5162 Yes, true!

[@abhinavsingh-zc2hk]

Thank You so much for this amazing technique.

[@AlgosWithMichael]

Most welcome 😊

[@sachinmamadapur3000]

Thanks for Nice Explanation :)

[@AlgosWithMichael]

No problem, thank you for watching!

[@sivan2878]

Good explanation bro. cool

[@ankoor]

Such a great explanation...

[@AlgosWithMichael]

Thank you!

[@just_another_curious_guy]

Clear explanation, Thank you

[@AlgosWithMichael]

You are welcome!

[@heisenberg1844]

Brilliant. Cheers mate.

[@AlgosWithMichael]

No problem 👍

[@swarnimvarshneya6944]

Hey.. I really can't get why after the second condition mid = mid+1 why it's the opposite. pl help anyone.

[@surbhiagarwal2322]

Ok, line 13. That's because after we determine the subarray is even, in the second condition the duplicate of mid is included in the right side. When we know that the duplicate is in the right side and still the right subarray is odd, that means the one single element is on the right side.

[@afk12217]

I used a different approach where I calculated the frequency of each element and checked it during each iteration and if it was not 2 then exited the loop and displayed that number....but I could not meet the runtime🤕🤕

[@AyaGamal2010]

There is a little better approach than Frequency, according to the sorted array so that you can do a linear search it will be a little better, but binary search is the best of them

[@arpit_singh10]

Amazing explanation

[@AlgosWithMichael]

Glad it was helpful!

[@yitingg7942]

Michael, can you please please do one for 93. Restore IP Addresses?

[@AlgosWithMichael]

Definitely!

[@vishnugajulapalli5305]

What is the white board that you are using?

[@AlgosWithMichael]

awwapp.com/

[@riyazbasha7982]

Can do it for operation

[@code7434]

Nice Explanation :)

[@AlgosWithMichael]

Thank you!

[@bismeetsingh352]

What do we do when both sides have odd no of elements?

[@AlgosWithMichael]

The logic should be the same if the entire array is odd

[@stlo0309]

i simply went for linear search lol

[@antarikshjain6802]

bhai thanks

[@psn999100]

AT this TS kzbin.info/www/bejne/anjMaah3r5tpbNU If we know that mid and mid + 1 are same, then we can check for evenness on the left side of mid, Similarly , as you explained , when mid and mid - 1 are the same, we can check for evenness on the right hand side of mid . That would avoid calculation for the evenness only on the right hand side by either doing numOfElements - 1 then % 2 or numOfElements % 2 without a -1 . Does that make sense ? Here is the code that passed Leetcode OJ int singleNonDuplicate(vector& nums) { int n = nums.size(); int low = 0; int high = n - 1; while(low < high){ int mid = low + ((high - low) >> 1); //If mid is itself the number we are looking for, return nums[mid] if(nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1]) return nums[mid]; if((mid - 1) >= 0 && nums[mid] == nums[mid - 1]){ int numElementsInRHS = high - mid; /*If the num of Elements in the RHS is even, then we know that our single elemnet cannot lie in that half*/ if(!(numElementsInRHS & 1)){ high = mid - 2; }else{ low = mid + 1; } }else if ( (mid + 1 < n && nums[mid] == nums[mid + 1])){ int numElementsInLHS = mid - low; if(!(numElementsInLHS & 1)){ low = mid + 2; }else{ high = mid - 1; } } } return nums[low]; }

[@AlgosWithMichael]

Yes it does, good catch! This problem is challenging because it has several edge cases I think.