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?
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!
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.
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.
weekend 27 July 2024 - Streak-1 I previously studied the binary search concept. I've now started Striver's playlist and just completed the first eight videos. Let's keep going!
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
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)
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.
i did it by length till mid approach(different way to look at same thing): 1) if length from low to mid is odd then storing only pairs will overflow the last pair such that num[m]==num[m+1] , so move right 2) if len from low to mid is even then storing only pairs will exhaust the length such that num[m-1]==num[m], so we move right
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 ...
@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 👍🏻👍🏻👍🏻.
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.
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.
Hey Striver this is one better code like i use mod operator to change the value of mid and i find ur approch is bit of lengthy and this has also O(log n) time and O(1) space complexity class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: if (len(nums)==1): return nums[0] left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 # Ensure mid is even so that it pairs with mid + 1 if mid % 2 == 1: mid -= 1 # If the pair is correct, the single element is to the right if nums[mid] == nums[mid + 1]: left = mid + 2 else: right = mid # left will be pointing to the single element return nums[left]
Can be done by XOR Just keep doing XOR from start to end of array, the element which appears only once will be the final result of XOR, rest will become 0 because A XOR A = 0 and 0 XOR A = A
Here's the code with same logic but simpler, class Solution { public: int singleNonDuplicate(vector& nums) { int low = 0; int high = nums.size() - 1; while (low < high) { int mid = low + (high - low) / 2; // Ensure mid is even for comparison with mid + 1 if (mid % 2 == 1) mid--; // If pair is found, the unique element is in the right half if (nums[mid] == nums[mid + 1]) { low = mid + 2; } else { // Otherwise, it's in the left half high = mid; } } return nums[low]; } };
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!
Outstanding 😊
Understood
Thanks bhai Ji😃
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?
Brute force Simplified:
int n = nums.length;
if(n == 1) return nums[0];
// O(n/2)
for(int i = 1;i
8 video at once. U r a legend for the community. Salute.
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!
thanks buddy
These made this ques just a piece of cake, thanks 👍🏻
Thanks
SOLVED THIS PROBLEM ON MY OWN , ANOTHER LEVEL OF SATISFACTION!!!
true
The way you explained the approach is just awesome.
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.
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.
weekend 27 July 2024 - Streak-1
I previously studied the binary search concept. I've now started Striver's playlist and just completed the first eight videos. Let's keep going!
wrote the code in one go, without any error, all the test cases passed, the satisfaction level is insane
apne is question ka logic khud banaya tha ya Striver bhaiyya ka video dekhne ke bad kiya tha ?
Striver you are the best, you clear even the smallest doubt, I always had a doubt to whether to take low< high or low
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
would'nt it take o(n/2)??
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)
it's obvious sir , how one can not understand this simplest explanation.......thankuu so much sir
The solution is great. More focussed on writing clean and readable code but not so much intuitive at first.
Ok so now onwards I will try to solve the edge cases before in the problem, this will allow me to focus on the main logical part and reduce stress.
00:00 Problem Explanation
02:42 Bruteforce (Approach 1)
04:52 Edge Cases
05:45 Binary Search (Approach 2)
20:27 Code
Good work 👍
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.
understood better than Scaler paid cource really Thank You
Eliminating left or right part based on even,odd logic is awesome :)
I really appreciate your enthusiasm and solutions.
i did it by length till mid approach(different way to look at same thing):
1) if length from low to mid is odd then storing only pairs will overflow the last pair such that num[m]==num[m+1] , so move right
2) if len from low to mid is even then storing only pairs will exhaust the length such that
num[m-1]==num[m], so we move right
Great video help me a lot I can't explain how much help it Thank you, sir.
Sir your really great and inspiring us to learn more about the coding,thank you so much 😢
Understood Sir, thanks a lot for this amazing video.
You are the king 👑 of coding striver
class Solution {
public:
int singleNonDuplicate(vector& nums) {
int ans=0;
for(int i=0;i
it has complexity of n
Understood! So amazing explanation as always, thank you very very much for your effort!!
We can write the same for loop loop ie. for(i=1; i
bhai lekin time complexicity zayada aa jaye gi
bhaiya, you are explaining the concept too good, Thank you so much.
I used xor method as a brute approach.
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 ...
yes bhaiya, plz make one on greedy
Understood , amazing explanation as always.
Thanks. Great way of explaining complex questions.
Thanks sir For This Amazing Explanation ❤❤❤❤
@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 👍🏻👍🏻👍🏻.
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.
its really great series ,Thanks Striver. Aap nhi hote to humara kya hota !!!!!!!!!!!!!!!!
sir please create a course on English speaking , i loved your way of speaking . you course will be brilliant one. it will be very helpfull❤❤❤❤
Mind blowing explanation.
23/01/25🎉8th video 🌄 straight 👍
Understood!!
we can also elimate a particular half on the basis of size of the array because single element will always be present in odd size array
understood ! great work buddy !
Hey striver please upload rest of the videos in this series.
Striver bhai maza hi aa gaya ...............one request to you is plzz bhai upload video alternate day😍
Thank you Striver...Understood everything
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.
amazing explanation thanks a lot
another solution is take xor of all the elements, TC ---> O(N), SC = O(1)
Amazing explanation ❣❣
Hey Striver this is one better code like i use mod operator to change the value of mid and i find ur approch is bit of lengthy and this has also O(log n) time and O(1) space complexity
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
if (len(nums)==1): return nums[0]
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
# Ensure mid is even so that it pairs with mid + 1
if mid % 2 == 1:
mid -= 1
# If the pair is correct, the single element is to the right
if nums[mid] == nums[mid + 1]:
left = mid + 2
else:
right = mid
# left will be pointing to the single element
return nums[left]
Striver one dumb question. When you started practicing DSA .Did you able to come up these tricks on your own at least for some?
Never bro it take several times to build a avg logic
Also me .... Curious about this......
Quite interesting question!
Can be done by XOR
Just keep doing XOR from start to end of array, the element which appears only once will be the final result of XOR, rest will become 0 because A XOR A = 0 and 0 XOR A = A
Sir series me maja aa raha .... Ab aage ka videos bhi upload kar do please🙏🙏🙏
We can also trim search further by putting left=2 , and right =n-3.
simple brute force is take xor of all element with xorr=0;
ultimately you will get single element
Yes but the reason of saying this brute force was to explain the thought process of binary search
@@takeUforward Okay, Thanks brother 🥰 You are doing a great work.
Such an incredible work!!
understood, for java people who are getting stuck in 25th test case, instead of using == operator, use .equals and it will pass.
Another solution:
int singleNonDuplicate(vector& arr)
{
int n= arr.size();
int l=0, r=n-1;
if(n==1){
return arr[0];
}
while(l
Please bro make a playlist on bit manipulation also thats a very difficult topic for us . Only you can make that easy.
Here's the code with same logic but simpler,
class Solution {
public:
int singleNonDuplicate(vector& nums)
{
int low = 0;
int high = nums.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
// Ensure mid is even for comparison with mid + 1
if (mid % 2 == 1) mid--;
// If pair is found, the unique element is in the right half
if (nums[mid] == nums[mid + 1]) {
low = mid + 2;
} else {
// Otherwise, it's in the left half
high = mid;
}
}
return nums[low];
}
};
Weirdly good question.
excellenttttt explaination..!!!!! Understood
thanks striver understood everything
Hey striver !! please upload rest of the videos too!! you are the best!!
Good explanation with dry run understood
superb explanation
How am I gonna get that observation of even odd, or odd ,even is it easy or am I the only one who felt amazed when Striver said that?
count me also
You're not alone.
I feel so dumb, I can't tell you! 😭
@@hidden_star14Same bro 😢
The way you say Single 😀, I don't think it's your problem Sir... right now
Although, kudos to your way of explanation...👏
you can also optimise the brute force by using two pointer technique.
UNDERSTOOD SIR
Understood ❤
Understood. Thanks a lot.
Simple O(n) in java
return arr.stream().reduce(0, (a,b) -> (a^b));
When to trim the right half and left half is not clear properly plz emphasise on that part only plzzzz and rest is just amazing love form our side
Here it was easy, so did not focus much, if you take a pen and paper, it is an easy problem! With problems we have, stay rest assured.
Understood, thank you.
that trimming❤❤
just awesome.
Done on 12 Jan 2025 at 13:57
Place : Study Room 2 , Hostel 5 , IIT Bombay
UNDERSTOOD
bhaiya please complete all lectures of all questions in a to z dsa as soon as possible it will be very helpful
MIND BLOWN AT @7:14 DAyummmmmmmm!!!!!!!
understoood!!
Understood @striver ❤🙌🥳
Great!💥
Kya mast thumbnail hai.. 🔥
My O(1) solution:
That Single element is me :)
Shandaar.
Understood✅🔥🔥
Understood😇😇
Plz upload rest of the video as soon as possible
thank you man
Understood ❤🎉
understood ❤
Thanks a lot Bhaiya
Understood sir 😇😊
Thankyou sir very helpful❤
Striver, when will you upload the remaining vedios of Binary Search playlist ?
Understood.
@takeUforward ,Since first two and last indices are same you can do low = 2 and high = arr.length-3 right?
yes
How can we do it through binary search if there are two single elements in an array ?