BS-8. Single Element in Sorted Array

Problem Link: bit.ly/42KKHj5
Notes/C++/Java/Python codes: takeuforward.org/data-structu...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction of Course

[@takeUforward]

The brute force can be better by just doing a XOR, but the reason we did that brute was to understand the binary search approach!

[@sagarpatle461]

Outstanding 😊

[@sudhanshushekhar4222]

Understood

[@DeepakKumar-uq9js]

Thanks bhai Ji😃

[@samuelfrank1369]

Will not the time Complexity differ? Brute force by xor will be O(n) where as this will be O(logn). Or are you with respect to the conditions that are being checked for logn times will be equivalent to O(n) time Complexity?

[@gauravpandey-fx9hk]

Brute force Simplified: int n = nums.length; if(n == 1) return nums[0]; // O(n/2) for(int i = 1;i

[@ratnadeepsaha7675]

8 video at once. U r a legend for the community. Salute.

[@yashmundada2483]

In short, If I'm on (even, odd), the element occurs after me, so eliminate everything before me (the left half) If I'm on (odd, even), the element occurred before me, so eliminate everything after me (the right half) Great video as always!

[@thefourhourtalk]

thanks buddy

[@lakshyagupta9435]

The way you explained the approach is just awesome.

[@AdityaKumar-be7hx]

Finished all 8 videos Striver :) When can we get rest of the videos? Thanks for putting in so much of effort to make these awesome DSA playlists available for free. All these (graph, DP, trie, tree, recursion, etc) are truly the best.

[@adityanigam8373]

Striver you are the best, you clear even the smallest doubt, I always had a doubt to whether to take low< high or low

[@cinime]

Understood! So amazing explanation as always, thank you very very much for your effort!!

[@charan123rams3]

Sir your really great and inspiring us to learn more about the coding,thank you so much 😢

[@raghavmanish24]

it's obvious sir , how one can not understand this simplest explanation.......thankuu so much sir

[@YogeshKumar-px5bd]

The solution is great. More focussed on writing clean and readable code but not so much intuitive at first.

[@ujjawal_]

00:00 Problem Explanation 02:42 Bruteforce (Approach 1) 04:52 Edge Cases 05:45 Binary Search (Approach 2) 20:27 Code

[@ratnadeepsaha7675]

Good work 👍

[@Vamshi9876]

Thanks. Great way of explaining complex questions.

[@arijitroy8652]

We can write the same for loop loop ie. for(i=1; i

[@Manasidas99]

Great video help me a lot I can't explain how much help it Thank you, sir.

[@bhupendramaurya6587]

bhaiya, you are explaining the concept too good, Thank you so much.

[@chphanisimha7802]

Such an incredible work!!

[@sayakghosh5104]

Mind blowing explanation.

[@user-sd1ou1db1p]

Another way to implement this without reducing the search space would be to use the condition (r>l+1), this way you are always ensuring that the search space is atleast of size 3. So now in the end, your anwer would be either arr[l] or arr[r] and you can check for both of them. Also you'll have to place a check for when the array size is 1. By using this technique, you won't have to write code for edge case and also you don't have to think about reducing search space. Although striver's approach of reducing search space was also amazing.

[@AbhishekSingh-cq2jx]

understood better than Scaler paid cource really Thank You

[@Shunya_Advait]

Understood Sir, thanks a lot for this amazing video.

[@bapanapallihemanth705]

You are the king 👑 of coding striver

[@manavsingh5919]

Thank you Striver...Understood everything

[@prathmeshparab7046]

Amazing explanation ❣❣

[@vijaynag7723]

its really great series ,Thanks Striver. Aap nhi hote to humara kya hota !!!!!!!!!!!!!!!!

[@58harshverma57]

Quite interesting question!

[@dayashankarlakhotia4943]

Good explanation with dry run understood

[@bhavyasrikanchi5753]

excellenttttt explaination..!!!!! Understood

[@samuelfrank1369]

Understood. Thanks a lot.

[@baderajesh23]

Eliminating left or right part based on even,odd logic is awesome :)

[@ayushgaurabh8604]

superb explanation

[@NazeerBashaShaik]

Understood, thank you.

[@kingbadshah452]

thanks striver understood everything

[@harshsolanki1058]

Two pointer method also gets the code done in O(log - base 2 - n). Keeping pointers low=0 and high=n-1 and doing simultaneous search and increasing or decreasing pointers by 2 @takeUforward

[@VasanthChoudary-uc5cz]

would'nt it take o(n/2)??

[@shibainu7500]

Two pointer is O(N) because you are traversing each element atleast once even though the number of iterations are n/2 In binary search, we completely reject half of the search space and that's why it is O(logN)

[@hiteshpanchal5772]

Striver bhai maza hi aa gaya ...............one request to you is plzz bhai upload video alternate day😍

[@vigneshwaran_2002]

Thankyou sir very helpful❤

[@shivajirao999]

wrote the code in one go, without any error, all the test cases passed, the satisfaction level is insane

[@sayanpradhan1366]

apne is question ka logic khud banaya tha ya Striver bhaiyya ka video dekhne ke bad kiya tha ?

[@chiragsharma8905]

00:06 Find the single element in a sorted array. 02:25 Identifying the single element in a sorted array using Brute Force 04:53 Apply binary search to optimize the code 07:16 Identifying the half and location of the single element. 09:30 Write a lot of edge cases and eliminate conditional statements 11:45 Performing binary search to find the single element in a sorted array 14:04 Identify if you are on the left half or the right half and eliminate accordingly. 16:19 Binary Search to find the single element in a sorted array. 18:42 In binary search, we eliminate the left or right half of the search space based on whether we are standing at an odd or even index. 20:42 The main focus of this video is on code readability, consistent use of variables, and understanding the concept of elimination in binary search. Crafted by Merlin AI.

[@tech1hutz]

Really Great explanation bhaiya ❤ pls can you also make a series for greedy algo questions and its approach obviously after completing this ongoing binary search series.....Its much needed coz your way of explaining approaching a problem really helps in building concepts as well as clear understanding of any problem.Thank you so much for all the series you made ...

[@neerajgupta9151]

yes bhaiya, plz make one on greedy

[@jeehub041]

Sir series me maja aa raha .... Ab aage ka videos bhi upload kar do please🙏🙏🙏

[@utsavseth6573]

Shandaar.

[@yogeeshrsyogeeshrs4204]

Understood ❤🎉

[@YourCodeVerse]

Understood✅🔥🔥

[@user-or5oz1pk2x]

Thanks a lot Bhaiya

[@abhay9994]

Thank You.

[@kiranmoura2974]

Understood ❤

[@harshilpatel3205]

Understood sir 😇😊

[@khalasianiket816]

understood ❤

[@hallupandet228]

Understood 🤗

[@UserUser-tn8tv]

Understood!

[@soumi6720]

understood!!

[@aakashsharma780]

Understood @striver ❤🙌🥳

[@RAJSINGH-mr7hq]

Superb 👌

[@adarshkumarrao3478]

UNDERSTOOD

[@aneesahmad05]

Excellent

[@adityarajsrivastava3291]

understood!

[@senseiAree]

I'm sorry for not being able to continue for some days. I had additional workload at my office which halted my learning curve but I made sure my daily streak is maintained in Leetcode and Coding Ninjas.

[@rakshanaravindran9809]

Understood!!

[@bishalsarkar9205]

Understood.

[@ashishranjan8350]

Hey striver please upload rest of the videos in this series.

[@mbm.editzz]

thank you sir

[@user-sm7zo5zd9t]

Understood

[@traymk]

Kya mast thumbnail hai.. 🔥

[@pihus3498]

Understoooood

[@rajeswarichalamcherla2860]

Understood !!!!

[@anshujaiswal5622]

Understood :)

[@dreamyme543]

Understood🙃

[@sulthan6131]

Love u lots❤

[@TrendyGamer007]

@takeUforward @striver please upload the remaining binary search videos as most of us have already finished watching all 8 videos … and the content was superb 👍🏻👍🏻👍🏻.

[@CoderGrow1]

thanks sir

[@abhishekkumar-fe8lw]

We can also trim search further by putting left=2 , and right =n-3.

[@sunnypunia6485]

bhaiya please complete all lectures of all questions in a to z dsa as soon as possible it will be very helpful

[@soumiyamuthuraj3516]

awesome

[@user-js1rx8rs9p]

understood bro 😎😎😎

[@pranavmisra5870]

understood😁

[@sagarshah5341]

MIND BLOWN AT @7:14 DAyummmmmmmm!!!!!!!

[@abhirajrohilla]

class Solution { public: int singleNonDuplicate(vector& nums) { int ans=0; for(int i=0;i

[@aayushgakhar3525]

it has complexity of n

[@arpitamanderna9111]

Hey striver !! please upload rest of the videos too!! you are the best!!

[@inderjeet09]

Please bro make a playlist on bit manipulation also thats a very difficult topic for us . Only you can make that easy.

[@shanmukhavuyyuri4414]

vere level

[@chethanprabhu4475]

I think we can consider low = 0 and high = arr.length - 1. Always there will be mininum 3 elements in array and hence mid can never be equal to low or high.

[@user-kx6fi8ou9f]

bhaiya bawal ho aap

[@suryasaimaheswar8636]

understood:)

[@Shivi32590]

thanku

[@divyadwivedi1527]

Plz upload rest of the video as soon as possible

[@himaniupadhyay8201]

Thanks Lord Striver

[@princebhanushali6255]

understood.

[@user-eq6ee8rd2h]

understood

[@seemameghasai6744]

@takeUforward ,Since first two and last indices are same you can do low = 2 and high = arr.length-3 right?

[@deepakojha3216]

yes

[@VINAYSINGH-wc8sq]

🔥🔥🔥

[@rahulkumarbarik7584]

That single element is me 🥲

[@VasanthChoudary-uc5cz]

you can also optimise the brute force by using two pointer technique.

[@AYJ959]

Simple O(n) in java return arr.stream().reduce(0, (a,b) -> (a^b));

[@MJBZG]

another solution is take xor of all the elements, TC ---> O(N), SC = O(1)

[@ashishpradhan6250]

understood😮‍💨😮‍💨

[@udatyadeb101]

understood, for java people who are getting stuck in 25th test case, instead of using == operator, use .equals and it will pass.

[@ashwath1914]

If we start with low = 0, high = n-1, the edge cases should be written inside and the code will look like this: int singleNonDuplicate(vector& arr) { int n = arr.size(); int l = 0, h = n-1, ans = -1; if(n == 1) return arr[0]; while(l

[@anupkhismatrao9280]

❤❤❤

[@adarshrajjaiswal9143]

My O(1) solution: That Single element is me :)

[@NavyaVedachala]

Is it possible to access the previous version of the A2Z DSA sheet? Links to problems and some videos are missing. There are also five problems missing. Is it possible to access these problems on a Google sheet if you have one until the glitch is fixed? Thank you! Loving the series

[@takeUforward]

5 problems are back now

[@SibiRanganathL]

Understood but need to revise.