I'm doing a bunch of these binary search problems, it's getting simpler and simpler, the whole is idea is to find the 'invariant' for parts of the array (left/right) and then defining 2 functions: is_goal_index(i) and is_index_too_high(i) (or is_index_too_low(i)), from there it's a breeze.
In the provided Python code, there isn't a risk of overflow because Python integers can grow arbitrarily large until memory is exhausted. However, in languages like C, C++, or Java, where integer types have fixed sizes, overflow can be a concern. In those languages, calculating the mid index with the formula (l + r) / 2 can cause an overflow if l and r are large enough. A common way to avoid potential overflow in such languages is to calculate mid as: makefile mid = l + (r - l) / 2; But again, in Python, you don't have to worry about integer overflow in this context because Python integers can grow as needed.
basically when size shrinks to 1, low and high will point to same index. now its upto the problem whethe rit wants to calculate mid when size==1 or not
Hey Neetcode. Thanks for the solution! But just to point something out, there's no integer overflow in Python! so its fine to do l + r // 2. Although it's good you pointed it out for those not using python
Had this in a google interview, I solved it but after the interview I realized I didn't cover a scenario which is why it didn't work out.. Thanks for explaining it so clearly
hey Neetcoder, I have a doubt regarding the way we are computing "leftSize". Shouldn't we need to subtract "l" from "m-1" and "m"? If "l" is not at 0, then "leftSize" wouldn't be calculated correctly.
The leftSize should always be relative to the whole array(which has the 'fixed' odd size). Take {1, 1, 2, 2, 4, 4, 5, 5, 9} as an example, after one iteration, it becomes l = 5, r = 8, m = 6; which means we have (0...5) elements left to the mid, and the odd search space exists in the other half(m...r). However, if you use the distance from l to m, then the search space will become 'l..m' which is wrong in this case.
I can see when I run this code on [1,1,2,3,3,4,4,8,8], the values of variables after one iteration is l=0, r=3, m=4 which has an array of [1,1,2,3], even though its returning the correct answer, It would have been great if you have addresed this in the video.
This is the approach i used 1. If the list contains only one number, it immediately returns that number because there are no other numbers to compare it to. 2. If the first number in the list is different from the second number, it means that the first number is the single non-duplicate, and the code returns it. 3. If the last number in the list is different from the second-to-last number, it means that the last number is the single non-duplicate, and the code returns it. 4. If neither of the above conditions is met, the code uses a binary search approach to find the single non-duplicate. It sets up two pointers, s and e, which represent the start and end of the search range. 5. It repeatedly calculates the middle index, mid, and checks if mid is an odd number and whether the number at index mid is the same as the number at index mid - 1 (and mid is not at the beginning of the list), or if mid is an even number and the number at index mid is the same as the number at index mid + 1 (and mid is not at the end of the list). If either of these conditions is true, it means the single non-duplicate is on the right side of mid, so it adjusts the s pointer to mid + 1. Otherwise, it adjusts the e pointer to mid - 1. 6. This process continues until the s pointer becomes greater than the e pointer. At that point, it returns the number at index s as the single non-duplicate element. def singleNonDuplicate(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] if nums[1]!= nums[0]: return nums[0] if nums[-1]!= nums[-2]: return nums[-1] s = 0 e = len(nums) while(s 0) or (mid%2 == 0 and nums[mid + 1] == nums[mid] and mid < len(nums) - 1): s = mid + 1 else: e = mid - 1 return nums[s]
why is the leftsize not subtracting the left pointer from mid - 1 ? (because left pointer can be in between the list somewhere and does not necessarily stuck at the first element)
Hey thanks for the solution. I have a doubt. In the array = [1,1,2,2,3,3,4,5,5], supposing mid = 4, leftSize will be equal to 4 which is even, so the right part will be the search space as it has 3 elements [4,5,5], but in that case shouldn't l = m+2? instead of m+1?
I wrote this code. This doesn't use binary search. Since we are comparing two elements all the time so we can iterate in the array by skipping two elements altogether. That makes the runtime O(log(n)). O(1) space complexity as well. Please feel free to ask if you have questions about the logic implemented def singleNonDuplicate(self, nums: List[int]) -> int: l = 0 r = len(nums) - 1
if len(nums) == 1: return nums[0]
if len(nums) == 0: return
while l != r: if l < r and nums[l] == nums[l+1]: l += 2 else: return nums[l] return nums[l]
in Python, the array length is indexed in the background. So when the len() function is called, I believe that makes it equivalent to O(1) every time it's called.
I'm doing a bunch of these binary search problems, it's getting simpler and simpler, the whole is idea is to find the 'invariant' for parts of the array (left/right) and then defining 2 functions: is_goal_index(i) and is_index_too_high(i) (or is_index_too_low(i)), from there it's a breeze.
These video make it almost as easy to solve as inputting the problem into ChatGPT.
In the provided Python code, there isn't a risk of overflow because Python integers can grow arbitrarily large until memory is exhausted.
However, in languages like C, C++, or Java, where integer types have fixed sizes, overflow can be a concern. In those languages, calculating the mid index with the formula (l + r) / 2 can cause an overflow if l and r are large enough.
A common way to avoid potential overflow in such languages is to calculate mid as:
makefile
mid = l + (r - l) / 2;
But again, in Python, you don't have to worry about integer overflow in this context because Python integers can grow as needed.
Nope , OverFlow of integers will occurs
for binary search how do we determine when to use "l
Here You wanna stop when l = r
same it seems a bit confusing to me as well
I'll never be able to write a bug free binary search in the first try
basically when size shrinks to 1, low and high will point to same index. now its upto the problem whethe rit wants to calculate mid when size==1 or not
One thing:
if left and right are mid+1 and mid-1, then l
Awesome solution as always . Thank you.
Your solution is so easy to understand!! Thank you!
Hey Neetcode. Thanks for the solution! But just to point something out, there's no integer overflow in Python! so its fine to do l + r // 2. Although it's good you pointed it out for those not using python
Very easy to understand, thank you so much!
you're the goat neetcode
Had this in a google interview, I solved it but after the interview I realized I didn't cover a scenario which is why it didn't work out.. Thanks for explaining it so clearly
what was the feedback? did you get an offer?
Clas-sic NeetCode Explanation - ❤
hey Neetcoder, I have a doubt regarding the way we are computing "leftSize". Shouldn't we need to subtract "l" from "m-1" and "m"? If "l" is not at 0, then "leftSize" wouldn't be calculated correctly.
i was wondering the same....
The leftSize should always be relative to the whole array(which has the 'fixed' odd size). Take {1, 1, 2, 2, 4, 4, 5, 5, 9} as an example, after one iteration, it becomes l = 5, r = 8, m = 6;
which means we have (0...5) elements left to the mid, and the odd search space exists in the other half(m...r). However, if you use the distance from l to m, then the search space will become 'l..m' which is wrong in this case.
Is overflow really a concern for this problem as these were the problem constraints?
Constraints:
1
Yeah it definitely wouldn't matter in this case but it's the type of trivia question your interviewer might ask.
Awesome solution and explanation. But one suggestion
instead of
if m - 1
This solution is so clever
i came up with the intution of binary search and etc really quickly and was just stuck on the edge cases and implemenation forever lol
I can see when I run this code on [1,1,2,3,3,4,4,8,8], the values of variables after one iteration is l=0, r=3, m=4 which has an array of [1,1,2,3], even though its returning the correct answer, It would have been great if you have addresed this in the video.
Yes you are right we should decrement m by 2 not one
What do you use to draw your explanations?
This is the approach i used
1. If the list contains only one number, it immediately returns that number because there are no other numbers to compare it to.
2. If the first number in the list is different from the second number, it means that the first number is the single non-duplicate, and the code returns it.
3. If the last number in the list is different from the second-to-last number, it means that the last number is the single non-duplicate, and the code returns it.
4. If neither of the above conditions is met, the code uses a binary search approach to find the single non-duplicate. It sets up two pointers, s and e, which represent the start and end of the search range.
5. It repeatedly calculates the middle index, mid, and checks if mid is an odd number and whether the number at index mid is the same as the number at index mid - 1 (and mid is not at the beginning of the list), or if mid is an even number and the number at index mid is the same as the number at index mid + 1 (and mid is not at the end of the list). If either of these conditions is true, it means the single non-duplicate is on the right side of mid, so it adjusts the s pointer to mid + 1. Otherwise, it adjusts the e pointer to mid - 1.
6. This process continues until the s pointer becomes greater than the e pointer. At that point, it returns the number at index s as the single non-duplicate element.
def singleNonDuplicate(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if nums[1]!= nums[0]:
return nums[0]
if nums[-1]!= nums[-2]:
return nums[-1]
s = 0
e = len(nums)
while(s 0) or (mid%2 == 0 and nums[mid + 1] == nums[mid] and mid < len(nums) - 1):
s = mid + 1
else:
e = mid - 1
return nums[s]
why is the leftsize not subtracting the left pointer from mid - 1 ? (because left pointer can be in between the list somewhere and does not necessarily stuck at the first element)
Hey thanks for the solution. I have a doubt. In the array = [1,1,2,2,3,3,4,5,5], supposing mid = 4, leftSize will be equal to 4 which is even, so the right part will be the search space as it has 3 elements [4,5,5], but in that case shouldn't l = m+2? instead of m+1?
here's another way:
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
def to_the_left(idx):
if idx == len(nums) - 1:
return True
elif idx % 2: # odd
return nums[idx] != nums[idx - 1]
else: # even
return nums[idx] != nums[idx + 1]
left, right, ans = 0, len(nums) - 1, -1
while left
this was so tough omg
Thank you so much
Man i fucking admire you
You should call left size as modified left size cause you are eliminating one variable from there.
just a trick i found out that appending None to the end of the array simplifies the conditions in the if statement
how?
How do you do the drawing so smooth? I really need it
hmm getting index out of range if I test with the case of only one element in the array (ie. [1])
I just learned Binary search algorithm even though i never tried it 💀
I wrote this code. This doesn't use binary search. Since we are comparing two elements all the time so we can iterate in the array by skipping two elements altogether. That makes the runtime O(log(n)). O(1) space complexity as well. Please feel free to ask if you have questions about the logic implemented
def singleNonDuplicate(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
if len(nums) == 1:
return nums[0]
if len(nums) == 0:
return
while l != r:
if l < r and nums[l] == nums[l+1]:
l += 2
else:
return nums[l]
return nums[l]
TimeComplexity of that is O(n/2)==O(n) not O(logN)
I am still confused how u got the leftSize
I literally just did this problem lol
That's because NeetcodeIO is doing leetcode daily challenge problems for almost a month now lol
My Solution :
class Solution {
public int singleNonDuplicate(int[] nums) {
int low = 0;
int high = nums.length-1;
int leftsize = 0;
while(low 0 && mid < nums.length - 1 && nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]){
return nums[mid];
}
else if((mid > 0 && nums[mid] == nums[mid - 1] && (mid - 1) % 2 == 0) || ( mid < nums.length - 1 && nums[mid] == nums[mid + 1] && (mid + 1) % 2 != 0)){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return nums[low];
}
}
for midpoint its not a bug in python
sorry but i copy that to use but it wrong in case 2: [3,3,7,7,10,11,11]
idk it wrong when i type but i have check too many. Thanks!
can anyone please tell me how to solve the below error!!!!!!!!
def singleNonDuplicate(self, nums: List[int]) -> int:
l,r=0,len(nums)-1
while l
if leftSize%2==0:
l = m+1
else:
r = m -1
here you did wrong do like above code
or follow same as above video solution
@@jayeshvarma8382 thank you bhai
Wow
yay first
here is my code no need to check for out of bound
l,r=0 , len(nums)-1
while l
it is correct
but len(n) will take O(n) time complexity 😆😆
in Python, the array length is indexed in the background. So when the len() function is called, I believe that makes it equivalent to O(1) every time it's called.