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).
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
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).
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.
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.
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.
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 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.
Hey There! I always look for your solutions in the RU-vid 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.
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)
We can use hash mapping to... _hash = {} for index, i in enumerate(numbers): complement = target - i if complement in _hash: return [_hash[complement] + 1, index+1] _hash[i] = index i = 2, complement = 9-2 => complement = 7. It will check key 7 is in the hash, if not it will add key 2 in hash i = 7, complement = 9-7 => complement = 2. Key 2 is present in hash, so it returns index of key 2 and i (add 1 at return because index is starting from 1)
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.
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
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.
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.
If you use binary search to find the starting point for pointer two you get a significant perf boost. Further, the statement you may assume that each input has exactly one solution means that the elements of the solution are unique, which means you dont increment the pointer by 1, you find the next unique value by binary search. Meaning the solution is log(n).
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 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).
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.
1:49 be careful. The statement says integers, so there could be negative numbers and hence there could perfectly be a combination (l,r) with r>T>=0>l (where l is the first element of the solution tuple and r the second, and T is our target value) such as (l+r)==T. Great video!!!!!! 😃😃💯 Edit: I had misunderstood the brute force strategy. I guess it can also work for negative numbers, too.
Wouldn't it also be possible to solve this using a tree to store numbers that we want to find ? We start with the first number, and store its "opposite" (in this example, as we see 1, we store 8 inside the tree), and we iterate until we reach a number which is in the tree. Here, it would be : - Add 8 to the tree - Add 6 to the tree - Add 5 to the tree - We inspect 5, and see that's it's already in the tree. Thus, we know that 9-5 = 4 was already in the array, thus we have our pair (4,5). Since we need the index of both, we can either use a label in the tree, a tuple, or just use a HashMap to store numbers that we want to hit as keys (and indexes as values).
@@MiloDC True. If memory consumption is considered, this solution is less efficient, even if the memory cost of a HashMap shouldn't be too high in the end
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.
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!
This can be further improve. Let say Input = [1, 4 ,6,7,9,10,13,16,17,20] Target = 10 Then we don't need to take last index of input array since 1010 and then follow with logic explained. This will give better performance if make this correct high index finding by using search like jump search since input is already sorted.
A quick performance increase for edge cases: Add a conditional that checks for length 2. Given we know that there has to exist a valid solution in each test set (as per instructions), a length of two means you can return those values without setting up the pointers. Also, modifying the original array values to instead be 1 and 2 and returning it will also lower space usage (but keep in mind this is not best practice). For Java I got a 99.2% runtime and 74% memory using these tricks. And I've found atleast in the case of leetcode that a lot of the easy/med problems can be slightly optimized when the solution is guaranteed to exist by doing this setup.
@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?
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.
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
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??
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.
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?
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.
You can use binary search to find an upper bound and exclude all numbers higher than the target at the start. The rest will still be O(n), with better average performance overall (constant factors are ignored by O-notation).
great solution ! ! I modified it by adding while numbers[r] == numbers[r + 1]: r -= 1 while numbers[l] == numbers[l - 1]: l += 1 when changing l and r this will avoid the checking for identical left or right values my time performance changed from 30% to 90%
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"); }
Funny thing: I have been forced to hunt for a job recently, and I have taken coding tests as part of the interview process. I always do poorly at these coding interviews, I *NEVER* do well. I am a non-degreed test engineer specializing in test automation. I have been doing it for 36 years. I have created both production tests and product verification tests, written in C, all these years. My verification tests tend to find the issues that no one else can isolate but that are still impacting the customer. My production tests work very reliably, allowing remote diagnostics, and no false-failures. I have saved companies I have worked for from gaining a reputation for shoddy product using my test systems. I have been accused of doing the impossible, but I was actually doing what I said I was doing and proved it. I am senior level, I am a mentor to other engineers, but I always fail these coding tests. I recently took a new job as a test engineer. After less than a month working my boss came to me and asked if I knew any other test engineers that work the way I do. Unfortunately, no, I do not. It's not just about being able to code, it's about attitude.
Why not use a dictionary with the .get() method so that you can get the numbers you need in the dictionary by storing the different as a key and value as the index so that way you can just .get() on the dictionary as you go through the list in O(n) time. The dictionary .get() should be 0(1) in python since the solution this way worked and was same speed as the video solution.
