Thanks for the video. I would add a if sum == target break as first condition in the while loop. Technically, the return [] should never be executed, and we should avoid such code (generally speaking, if the code is there - it must be executed in some edge cases, and I prefer to not have incorrect code, even if it will never be reached).
Looks like sub-linear is possible, instead of moving the pointers to the next position, do a binary search for the number you need or the one right after it.
@@zwanchis how does that improve performance? I could possibly see readability, but isn't it just the mirror of the given array? That would mean you just swap certain operations, right?
@@aminafounoun Time complexity could be sub-linear by changing the proposed algorithm, of complexity O(N), to instead of moving the right or left pointers just by one, doing a binary search for the value that will be needed. Using the above example, left pointer -> 1, right pointer could be found by looking for 8 (= 9 - 1) using a binary search. The result of the search will yield 7, the entry available in the next position. Then, search for 2 (= 9 - 7), etc. The boundaries of the search narrowing each time. With the resulting complexity O(LogN), because we did not need to examine every position and taking advantage of the sorted order of entries.
@@DavidDLee This does multiple binary searches though, so it will only be O(log N) if the number of binary searches is constant, i.e. the number of searches doesn't increase as N increases. I don't know if that's true for the average case, but you can find a worst- case example that is O(N log N). When nums = [1,3,5,6,7,9,11] and target = 13, the left and right pointers alternate between which one has to move. It ends up doing approximately N binary searches. Even though the array to search decreases by 1 each time, summing up log N + log (N-1) + ... + 2 + 1 is still O(N log N).
This looks good for small arrays, but my guess at a solution for a bigger array would be to use a log search for the number closest to half of the target, eliminating any Halves of the given array who's numbers were above the target, and then use the same method you did to find the pair, except go outward from the middle, where the numbers closest to half of the target are, instead of going inward from the ends. In good cases that would reduce the amount of searches you would need, although it would give an upper bounds of a n log n runtime if none of the elements were higher than the target.
Hey, thats a good thought! but that wouldn't work if say, all the numbers in the middle 50% are even, and all the numbers in each outer quartile were odd.
What about a binary search for the complement? Where complement = target - first. Starting from first, search for the complement, if not available, move on to the next value. This o(n) as well.
I think the best way to do this is to binary search for the index of the first number greater than the target. (Ignore this step if the target is greater than the largest element) then do the double pointer method from there.
I'm shit at programming, so I'd love to hear from someone if the solution I came up with actually works (memory wise its less efficient then the solution here guaranteed) My solution is basically this: Subtract each number in the array from the target and save the result (probably in a hashmap with the key being the index) and if, at any point, the next number is equal to ine if the reaults, those are the correct numbers. So basically "Target - num[n] = result[n]", result get saved, and if num[n+i] = result[n] thats the solution. Logically it makes sense, I have no idea if there is a proper (and efficient) way to code this though. Could someone tell me if that works?
This video is for "LeetCode 167. Two Sum II - Input Array Is Sorted". As the problem name says, the input is guaranteed to be sorted. There's a problem where the input is not sorted, "LeetCode 1. Two Sum", and there's a different video for that with a different solution.
The solution itself is quite intuitive, the nontrivial part of this question is explaining why it always works (which I'm pretty sure the interviewer will ask). More specifically, at each step we only consider moving the lower pointer up or the upper pointer down (in order to increase or decrease the sum resp), why do we not need to consider moving both pointers up or down at the same time (which might change the sum)? Proof: Suppose exists a sorted array of n such that exists 2 indexes a,b that give the required sum, WLOG a
u an actual NEET? i am rn but only b/c i chose a shitty major i'm trying to get into CS industry after this by doing more leetcode and self-teaching algos do u have a discord?
Haha, technically I am a NEET right now, but maybe not in its true meaning. Good luck with self-teaching, it's definitely possible because many people have been successful doing that.
I considered two pointers at first but for some reason decided that it wouldn't work. I went with finding the complement by binary search which was kind of an overkill but gave me an obviously suboptimal O(n*logn). Still, better than brute force.
Not sure if someone else mentioned this, but it seems to me that you could have also excluded 10 in the first round and 7 in the second round. If the array is sorted and 1 + 10 is greater than the target, then nothing after 1 can be added to 10 either. Same for 7 summed with anything after 3.
I mean yeah, but why waste time with that? It's now like they are thousands of extra iterations. Although I agree with the simple exclusion of >target (9).
Key thing I think you missed deleting array items is that you could have deleted, for example, the 10 in the first one, because if 1+10 > 9, then clearly n+1+10 is going to be correct.
@NeetCode Can I ask if it would be acceptable to use the same theory behind the first Two Sum question (Leetcode 1) in this problem? Logging the difference between the target and the current number in a hashmap would also work no?
The wording of the problem on leetcode is extremely confusing for such a simple problem and overcomplicated with making the array 1-indexed without it meaningfully changing the problem.
Hey There! I always look for your solutions in the RUclips first and then I move it to someone if I couldn't find your solution available to understand the leet code challenges. Thank you for all your efforts to demonstrate the leet code solutions. It really help us. Thank you! Please post as many solutions you can from leet code.
Quick note, this technique only works assuming the list is sorted. So in an interview you have to ask if the indices of the original list being returned is one of the constraints. Given that when you sort the original list the indices of what add up to the target will change.
my code TLE'd in c++ class Solution { public: vector twoSum(vector& numbers, int target) { vector ans; int i=0; int j=numbers.size()-1; int sum=0; while(itarget){ j--; } else if(sum
y don't we use the answer from ruclips.net/video/KLlXCFG5TnA/видео.html class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: hashmap = {} for i in range(len(numbers)): complement = target - numbers[i] if complement in hashmap: return[hashmap[complement]+1,i+1] hashmap[numbers[i]]=i
I managed to do this very elegantly without looking at any help. I'm proud of myself, a week ago I was very bad at this. Here's my solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: i = 0 j = len(numbers) - 1 while numbers[i] + numbers[j] != target: if numbers[i] + numbers[j] < target: i += 1 else: j -= 1 return [i + 1, j + 1] It's a little bit more elegant as we don't compare the index numbers but the values of the array in those indexes. That's the condition of our while loop. I find it more readable this way. Either way, great explanation as always.
@@brhnkh: If I got the question right, the input is expected to contain numbers that will always add up to target. With that assumption, there cannot be a single number as input. So nums = [3, 3], target = 6 can be a valid example I think.
This is satisfyingly efficient. Note that you can initialize r to the smaller the length of the array or the target number. The smallest possible values in numbers[0] and numbers[x] are 1 and x-1, thus the smallest sum is x, and r will always be
@@romanpisani8157 It is correct, a non-descending array of integers can include duplicate values. However, note that you're responding to an old comment and there is a lot of evidence that the problem details have changed more than once over the years. I may well have made a mistake back then, but we can't really know without the context I was in at the time.
So are we supposed to come up with these solutions ourselves or are we supposed to just do a bunch of questions and memorize these solutions and use them on similar questions that come up with different wording??
We can stop at 10 from the first iteration since 1+ 10 is 11. No need to continue to 11 as you mentioned and also not to consider 10. So the second iteration array is 3457
Hmm, I'll take a crack at it before watching the rest. if (size < 2) throw error("invalid input"); int iLow = size / 2; int iHigh = iLow + 1; while (true) { int sum = data[iLow] + data[iHigh]; if (sum == target) return {iLow, iHigh}; if (sum < target) iHigh++; else if (sum > target) iLow--; if (iLow < 0 || iHigh >= size) throw error("no solution"); }
One improvement I'd suggest: Lets say your array in all the numbers 1 through 1 million, and you target is 10. You'd waste a lot of time decrementing the right pointer one step at a time. Alternately, if your target is 1.9 million, you waste time slowly incrementing the left pointer. It would be more efficient to use a gallop search to find the next element to stop at each time.
@@MoogieSRO It's where you jump 1 item, then 2, then 4, then 8, etc.. Basically, you know what a binary search is? Where you know that x is too low and y is too high, so you check halfway between them? And if the middle point is too low, it becomes your new x, and if its too high, it becomes your new y? Well, gallop search is what you use when you have an x which is too low, but don't know where the y which is too high starts.
When you have sorted array, and target= 9, you can throw away all elements from array at the beginning (before running algorithm code), which are greater than target (15 for this example), because we are doing Two Sum (addition with two numbers)
Wouldn't this be similar but slightly more efficient? (assumes 1-based array indexes) n=# array elements for x from 1 to n-1 for y from x+1 to n if value[y]>=9-value[x] break is value[y]=9-value[x] DONE - FOUND IT!
Binary search is a good option to consider when you see a sorted array. But what exactly are you planning to search for? You need to find two values that sum up to the target.
Can't this also be solved with the other twoSum algorithm where we use hashmaps? I used it and it still beats 96% of the submitted solutions, why do we opt for two pointers here? thanks in advance
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
the video's title should be 167 instead of 157🤣
@@liairi6834 Just fixed, surprised no one noticed until now lol
Do you use blue switches???
Thanks for the video. I would add a if sum == target break as first condition in the while loop. Technically, the return [] should never be executed, and we should avoid such code (generally speaking, if the code is there - it must be executed in some edge cases, and I prefer to not have incorrect code, even if it will never be reached).
One of the few leetcode mediums I've been able to solve alone, just by watching your videos with similar problems. Really appreciate the help
high quality explanations, honestly way better than most channels on this site. great work
...and on top of that - high quality microphone setup
Looks like sub-linear is possible, instead of moving the pointers to the next position, do a binary search for the number you need or the one right after it.
Binary search is possible, you can even invert the list to improve performance
@@zwanchis how does that improve performance? I could possibly see readability, but isn't it just the mirror of the given array? That would mean you just swap certain operations, right?
What about time complexity? Are you going to apply binary search for each element?
@@aminafounoun Time complexity could be sub-linear by changing the proposed algorithm, of complexity O(N), to instead of moving the right or left pointers just by one, doing a binary search for the value that will be needed. Using the above example, left pointer -> 1, right pointer could be found by looking for 8 (= 9 - 1) using a binary search. The result of the search will yield 7, the entry available in the next position. Then, search for 2 (= 9 - 7), etc. The boundaries of the search narrowing each time. With the resulting complexity O(LogN), because we did not need to examine every position and taking advantage of the sorted order of entries.
@@DavidDLee This does multiple binary searches though, so it will only be O(log N) if the number of binary searches is constant, i.e. the number of searches doesn't increase as N increases.
I don't know if that's true for the average case, but you can find a worst- case example that is O(N log N).
When nums = [1,3,5,6,7,9,11] and target = 13, the left and right pointers alternate between which one has to move. It ends up doing approximately N binary searches.
Even though the array to search decreases by 1 each time, summing up log N + log (N-1) + ... + 2 + 1 is still O(N log N).
You’re literally saving my life rn🙏🏾thank you for these videos
Happy to help!
Figuratively! Unless your life literally depends on clever pointer manipulation...
@@DrewLevitt lol! figuratively of course
This looks good for small arrays, but my guess at a solution for a bigger array would be to use a log search for the number closest to half of the target, eliminating any Halves of the given array who's numbers were above the target, and then use the same method you did to find the pair, except go outward from the middle, where the numbers closest to half of the target are, instead of going inward from the ends.
In good cases that would reduce the amount of searches you would need, although it would give an upper bounds of a n log n runtime if none of the elements were higher than the target.
Hey, thats a good thought! but that wouldn't work if say, all the numbers in the middle 50% are even, and all the numbers in each outer quartile were odd.
What about a binary search for the complement? Where complement = target - first.
Starting from first, search for the complement, if not available, move on to the next value.
This o(n) as well.
That will be O(n.log n) as binary search is O(log n) itself and you might have to search n-1 times in the worst case.
You got a new subscriber in your first couple of minutes! I would love to see & hear more from you, great!
Why not use binary search on the items after the current ?
How did you think of using two pointers? I used binary search and wrote a really ugly code
generally speaking you can use two pointer solutions for any of the various Two Sum style problems
love your channel. really well done videos. hoping to get FANG now :)
How's it going?
Yo????
Where are you, made it?
Your solutions are the best. Thanks!
Amazing explanation !
@neetcode if happen to read this! THANK YOU FAM!
NeetCode for president.
I think the best way to do this is to binary search for the index of the first number greater than the target. (Ignore this step if the target is greater than the largest element) then do the double pointer method from there.
Wouldn't that be O(nlogn) complexity, though?
@@reidyoung298 yes, it runs in O(n * log(n)).
Wouldnt it cut the n time in half on average and convert that first half to log n?
I bet this can be done with two binary search pointers, ill think abt it and get back to you
Love your videos, they are amazing!
Great! as always!
nice explanation, thanks!
why didnt we use binary search here ??
Thanks for the explanation!
I'm shit at programming, so I'd love to hear from someone if the solution I came up with actually works (memory wise its less efficient then the solution here guaranteed)
My solution is basically this:
Subtract each number in the array from the target and save the result (probably in a hashmap with the key being the index) and if, at any point, the next number is equal to ine if the reaults, those are the correct numbers.
So basically "Target - num[n] = result[n]", result get saved, and if num[n+i] = result[n] thats the solution.
Logically it makes sense, I have no idea if there is a proper (and efficient) way to code this though. Could someone tell me if that works?
This was genius.
So its literally just a binary search?
those variable names hurt. Ever heard of clean coding?
dudeee whatttt this is so ginormous brain
But the given list is not sorted. What is this? It's a completely different problem
two sum 2 is sorted
Why is this a medium now?
Real question. This should be an easy. It's a standard problem in the realm of two-pointer problems.
How is this not an easy question?
I just solved this question alone😃 but still came here to learn how to think better
Man, why are interviews so far from what they should be.
This method wont work for unsorted arrays, and hence wont satisfy all the test cases.
This video is for "LeetCode 167. Two Sum II - Input Array Is Sorted". As the problem name says, the input is guaranteed to be sorted.
There's a problem where the input is not sorted, "LeetCode 1. Two Sum", and there's a different video for that with a different solution.
//O(log n) best solution 🎉
if (numbers.size() target)
r = mid - 1;
else
r--;
}
}
return {-1, -1};
I like how you also included the brute force solution. Thanks a lot!
No way amazon asked this simple question 😂, I took 2 coding interviews with amazon and its always matrices or something difficult.
what was the question?
@@robr4501 we cannot share but mine were def on leetcode. Just different wording
I got house robber on one of my FAANG interviews
@@nero9985 which FAANG? Curious who's still asking DP
@@PippyPappyPattersoneveryone is asking dp
The beauty about these challenges is that the code is simple but the logic to get to an optimal solution is quite complex.
The solution itself is quite intuitive, the nontrivial part of this question is explaining why it always works (which I'm pretty sure the interviewer will ask).
More specifically, at each step we only consider moving the lower pointer up or the upper pointer down (in order to increase or decrease the sum resp), why do we not need to consider moving both pointers up or down at the same time (which might change the sum)?
Proof: Suppose exists a sorted array of n such that exists 2 indexes a,b that give the required sum, WLOG a
I was wondering this exact same question! Thank you so much!
So, in 2sum 2 as compared to 2sum, we use the fact that the array is sorted to take the best-case space complexity from O(n) to O(1).
u an actual NEET? i am rn but only b/c i chose a shitty major
i'm trying to get into CS industry after this by doing more leetcode and self-teaching algos
do u have a discord?
my discord is hydro#3651
Haha, technically I am a NEET right now, but maybe not in its true meaning. Good luck with self-teaching, it's definitely possible because many people have been successful doing that.
I considered two pointers at first but for some reason decided that it wouldn't work. I went with finding the complement by binary search which was kind of an overkill but gave me an obviously suboptimal O(n*logn). Still, better than brute force.
This question is now a Medium! Lol, LeetCode should make it possible for users (at least paid ones) to have an input on the difficulty of problems.
Really clear explanation with no useless information and a smart solution on top of that.👍
Not sure if someone else mentioned this, but it seems to me that you could have also excluded 10 in the first round and 7 in the second round. If the array is sorted and 1 + 10 is greater than the target, then nothing after 1 can be added to 10 either. Same for 7 summed with anything after 3.
This still results in O(n^2), right?
@@jimmy090 Yup
I mean yeah, but why waste time with that? It's now like they are thousands of extra iterations. Although I agree with the simple exclusion of >target (9).
@@TheNuub63 That works for this case but not for cases with negatives on the left side unless I am misunderstanding your implications.
@@daimeunpraytor7984 if there are negative numbers you are correct! We would have to check everything basically!
Key thing I think you missed deleting array items is that you could have deleted, for example, the 10 in the first one, because if 1+10 > 9, then clearly n+1+10 is going to be correct.
The two pointers solution was actually pretty neat 👌
*neet
my first leetcode medium level question i was able to solve by my own.🤣
@NeetCode Can I ask if it would be acceptable to use the same theory behind the first Two Sum question (Leetcode 1) in this problem? Logging the difference between the target and the current number in a hashmap would also work no?
This was surprisingly easy. I doubt it's a real interview question.
Maybe for interns or new grads
for phone screen interviews and this is not the final solution. They are actually looking for binary search with two points.
Brilliant mate, consistent quality explanation from the start!
The wording of the problem on leetcode is extremely confusing for such a simple problem and overcomplicated with making the array 1-indexed without it meaningfully changing the problem.
wouldn’t it be faster if we cut out the numbers that are greater or more than target as well?
Had I done this I would have coded option #1 and felt good about myself. Clearly I'm a beta programmer and not a chad coder.
Wait a minute…ARE YOU USING A MOUSE TO WRITE AND DRAW ALL THIS??
best LC python solutions. I recommend this to everyone!
Great video. Thanks! I have a dumb question. Why couldn't I use the same method from the first version of two sum to solve this?...
I used the method from the first version and added +1 to returns and it worked fine
This one is sorted, so the first one using this solution will miss the mark
This problem says you must use O(1) space while the Traditional 2sum uses a hashmap
Why didn't we eliminate numbers that are larger than target? Aren't all numbers positive?
My first medium difficulty question that i solved intuituvely
target = 9
lst = [1,4,5,7,10,11]
for i, el in enumerate(lst):
if (target-el) in lst:
val1 = i
val2 = lst.index(target-el)
break
print(val1+1,val2+1)
Great answer. But time complexity is O(n²). Since the index() takes O(n) time complexity ✨
Hey There! I always look for your solutions in the RUclips first and then I move it to someone if I couldn't find your solution available to understand the leet code challenges. Thank you for all your efforts to demonstrate the leet code solutions. It really help us. Thank you! Please post as many solutions you can from leet code.
Quick note, this technique only works assuming the list is sorted. So in an interview you have to ask if the indices of the original list being returned is one of the constraints. Given that when you sort the original list the indices of what add up to the target will change.
wait does this also work on unsorted arrays? or just only on sorted arrays? i don't think [3,2,4] would work... if the target is 6...
Only sorted
That is very sweet solution! Loved it while you explain and arrive at the solution. Keep up the great work!
my code TLE'd in c++
class Solution {
public:
vector twoSum(vector& numbers, int target) {
vector ans;
int i=0;
int j=numbers.size()-1;
int sum=0;
while(itarget){
j--;
}
else if(sum
if(sum==target){
ans.push_back(i+1);
ans.push_back(j+1);
break;
}
fixed it :)
y don't we use the answer from ruclips.net/video/KLlXCFG5TnA/видео.html
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(numbers)):
complement = target - numbers[i]
if complement in hashmap:
return[hashmap[complement]+1,i+1]
hashmap[numbers[i]]=i
Abysmal space requirement
came to solve this problem after i failed miserably to solve 3sum alone
Why why why didn't I figure that out. Thank you master
Thank you, this was very helpful.
One of the most impressive parts of your leetcode skillz is the ability to draw everything cleanly using a mouse lol
He's probably using a tablet with a stylus.
I managed to do this very elegantly without looking at any help. I'm proud of myself, a week ago I was very bad at this.
Here's my solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i = 0
j = len(numbers) - 1
while numbers[i] + numbers[j] != target:
if numbers[i] + numbers[j] < target:
i += 1
else:
j -= 1
return [i + 1, j + 1]
It's a little bit more elegant as we don't compare the index numbers but the values of the array in those indexes. That's the condition of our while loop. I find it more readable this way.
Either way, great explanation as always.
nums =[3], target =6 fails this
@@brhnkh: If I got the question right, the input is expected to contain numbers that will always add up to target. With that assumption, there cannot be a single number as input. So nums = [3, 3], target = 6 can be a valid example I think.
@@messagegc you're right! the problem actually states len.nums >=2
heroic explanation
Wait this was an easy question? It's labeled a medium now lol
This is satisfyingly efficient. Note that you can initialize r to the smaller the length of the array or the target number. The smallest possible values in numbers[0] and numbers[x] are 1 and x-1, thus the smallest sum is x, and r will always be
This doesn't work if the array can contain negative numbers. LeetCode's constraints say that -1000
non decreasing does not mean the same thing as increasing. It could be the same number many times
@@romanpisani8157 It is correct, a non-descending array of integers can include duplicate values. However, note that you're responding to an old comment and there is a lot of evidence that the problem details have changed more than once over the years. I may well have made a mistake back then, but we can't really know without the context I was in at the time.
What would be the time complexity if i solved using hashmap?
Time of O(n) but the space would be O(n), but with the 2 pointer method, the space is O(1).
I get that we can use this solution, but why don’t we use the Hashmap one pass solution? Is it because we occupy O(n) space and that isn’t optimal?
this is now labeled as a 'medium', not sure why
Great explanation!
That's a lot easier than I thought it'd be! They mark it as medium, but it's almost like doing a binary search.
So are we supposed to come up with these solutions ourselves or are we supposed to just do a bunch of questions and memorize these solutions and use them on similar questions that come up with different wording??
while returning y u added 1 to both pointers
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i = 0
j = len(numbers)-1
while numbers[i] + numbers[j] != target:
if numbers[i] +numbers[j] > target:
j -= 1
elif numbers[i] +numbers[j] < target:
i += 1
return [i+1,j+1]
i just don't understand why we return l+1 and r+1 please tell me?
1
This guy talking and typing.. TOP ASMR CHANNEL!!!
We can stop at 10 from the first iteration since 1+ 10 is 11. No need to continue to 11 as you mentioned and also not to consider 10. So the second iteration array is 3457
It feels so good when you solve using the exact method I was thinking about!
Somehow this has grown into a Medium problem in LC. You might want to move it to another playlist.
This video was amazing! Thank you, thank you & thank you! (or thank you * 3 :))
Please continue to upload videos like this
Hmm, I'll take a crack at it before watching the rest.
if (size < 2) throw error("invalid input");
int iLow = size / 2;
int iHigh = iLow + 1;
while (true) {
int sum = data[iLow] + data[iHigh];
if (sum == target) return {iLow, iHigh};
if (sum < target) iHigh++;
else if (sum > target) iLow--;
if (iLow < 0 || iHigh >= size) throw error("no solution");
}
oh and insert one more bounds check if size == 2
One improvement I'd suggest: Lets say your array in all the numbers 1 through 1 million, and you target is 10. You'd waste a lot of time decrementing the right pointer one step at a time. Alternately, if your target is 1.9 million, you waste time slowly incrementing the left pointer. It would be more efficient to use a gallop search to find the next element to stop at each time.
What's a gallop search?
@@MoogieSRO It's where you jump 1 item, then 2, then 4, then 8, etc..
Basically, you know what a binary search is? Where you know that x is too low and y is too high, so you check halfway between them? And if the middle point is too low, it becomes your new x, and if its too high, it becomes your new y? Well, gallop search is what you use when you have an x which is too low, but don't know where the y which is too high starts.
@@macdjord Ahh I see. Thanks for the explanation!
When you have sorted array, and target= 9, you can throw away all elements from array at the beginning (before running algorithm code), which are greater than target (15 for this example), because we are doing Two Sum (addition with two numbers)
Negative integers tho…
If I got asked this question on an interview, I'd do a backflip
What if there is duplicate numbers in the array? should we add one more condition to deal with that?
Wouldn't this be similar but slightly more efficient? (assumes 1-based array indexes)
n=# array elements
for x from 1 to n-1
for y from x+1 to n
if value[y]>=9-value[x] break
is value[y]=9-value[x] DONE - FOUND IT!
not more efficient or even viable. consider negative numbers.
You wouldnt want to consider the 10 value either because its larger than the target value no?
since it's sorted, why don't try binary search?
Binary search is a good option to consider when you see a sorted array. But what exactly are you planning to search for? You need to find two values that sum up to the target.
the non zero indexing is weird.
Slower than 70% of submissions.
Leetcode "slower than"s and "faster than"s are almost randomly generated in my opinion
Cant, we use the binary search to search the target?
You could, but there's two targets so I think the time complexity would be nlogn
difficult level changed from (Easy to Medium)
Can't this also be solved with the other twoSum algorithm where we use hashmaps? I used it and it still beats 96% of the submitted solutions, why do we opt for two pointers here? thanks in advance
O(n) vs O(1) space for the same O(n) time, so this solution is strictly better