int left=0; int right=numbers.length-1; int[] res=new int[2]; while(leftnumbers[left]){ left++; }else{ right--; } } return res; this would be my code for this question i just wrote here i didnt submit the soultion
He left it out of the description, but the problem also says its a 1-indexed array. So if you're coding in a 0-indexed language such as Python, C, JavaScript, etc, you need to adjust the indexes by 1. The problem actually says : "Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2."
if only two numbers, then extremely simple. In general, suppose we want to look for numbers, no matter how many, that have the summation equal to a given number k, then a fundamental way is to apply dynamic programming.
Quick question, does it work if you just have a dictionary(hashmap)? Like index through each of the element A[i] then store (target - A[i]) as the key and its index as the value. Then return the index if found in the hashmap. This is O(n) too I believe. P/s: if it need constant space then 2 pointer is the way to go.
i would just do like put p1 on 0 then p2 from 1-len of list then if sum not found, p1 goes to 1 and p2 starts from 2-len of list, this continues until sum is found then if p1 == p2: return p1, p2 works on both two sum and two sum II
In BS, you're eliminating half the list with each iteration, resulting in O(logN) time. With TP, you're still iterating through the whole list, but with 2 pointers instead of one. This results in O(N) time if you're not nesting pointer iterations.
That would still get you a solution, but it's less efficient, and the actual problem description on Leetcode says that your solution "must use constant space", althought it doesn't enforce that. Using a hashmap would be O(n) space, not O(1)
You use two sum. Where you basically go and and get the first number add it with everything if no sum equals target then you go to de next number adding it with everything but skipping the first number
@@Progamertoatoh that would n**2 time complexity or basically we can convert that normal two sum to this one by sorting making whole complexity as nlogn. Just thinking if we can do like AVL and work on some way to get answer in O(n)
@@GregHoggmake sense. That should be worst case o(nlogn) too if we assume hashmap has so much collision or we using balanced tree internally for hashmap thus eventually making it O(nlogn). Best case O(n)/ avg case O(n) definitely. How about three sum say finding triplet a+b+c = 0. Can we do something using hashmap? Maybe like this: Say b+c = k. Then find for a = -k. We can get all combinations of b and c as nc2 or O(n^2) and then find if -k exists in hashlist of a, just that we need to keep track of not using same element of b and c. This could be one way from two pointer but i feel using standard two pointer is much better
Master Data Structures & Algorithms For FREE at AlgoMap.io!
int left=0;
int right=numbers.length-1;
int[] res=new int[2];
while(leftnumbers[left]){
left++;
}else{
right--;
}
}
return res; this would be my code for this question i just wrote here i didnt submit the soultion
I saw you using n as in r = n - 1 before declaring that n = len(numbers)
Good job
Yeah poor job indeed lol
First thing I noticed too
Confuse me a bit at first but the idea was nice though
This is a great teaching question. I love it when an answer has a (more or less) optimal solution that uses two pointers.
Yeah it feels very elegant indeed 😊
Also, please send an email to greg.hogg1@outlook.com if you're interested in 1 on 1 sessions with me to learn data structures and algorithms :)
How much would you charge?
Would be great if you displayed the time complexity in the end
O(n) :)
Still O(n) but with O(1) space
Why do we return l+1, r+1 and not l, r
that’s a very good question
He left it out of the description, but the problem also says its a 1-indexed array. So if you're coding in a 0-indexed language such as Python, C, JavaScript, etc, you need to adjust the indexes by 1.
The problem actually says : "Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2."
This. The dumb question asks for it +1 for some silly reason
Doing Great bro ❤
Thanks a ton!!!
if only two numbers, then extremely simple. In general, suppose we want to look for numbers, no matter how many, that have the summation equal to a given number k, then a fundamental way is to apply dynamic programming.
Or just backtracking, yeah! :)
@@GregHogg I assume they are the same thing? Practically, to perform DP, one has to do backtracking.
Binary search or Two Pointer : TC => O(nlogn) SC => O(1) (When Array not sorted)
TC => O(n) SC => O(1) (sorted array)
Hash Map: TC => O(n), SC => O(n)
No no two pointer is o(n) time and o(1) space
@@GregHogg sorry i made a mistake, i think array was'nt sorted.
You're right.
So the reason we used two point here is becoz this is sorted right? Not in two sum 1 as it wasn't sorted?!
Quick question, does it work if you just have a dictionary(hashmap)? Like index through each of the element A[i] then store (target - A[i]) as the key and its index as the value. Then return the index if found in the hashmap. This is O(n) too I believe.
P/s: if it need constant space then 2 pointer is the way to go.
If the array was not sorted, the hashmap approach would be O(N) and the two pointers approach would be O(N*Log(N)).
You're super right, the point of this solution is to use constant space:)
But the array is unsorted to begin with I think hashmap would be a better solution
i would just do like put p1 on 0 then p2 from 1-len of list then if sum not found, p1 goes to 1 and p2 starts from 2-len of list, this continues until sum is found
then if p1 == p2: return p1, p2
works on both two sum and two sum II
Does it? Did you test it?
@@GregHogg not yet, this is a O(n²) solution, so use a hashmap
this is like L: 0 R: 1-len(numbers)
then L+1 if L+R is not target, repeat till found
also can you break down linked lists
How does your code work if you declarated r before n if the declaration of r is dependent of n?
It doesn't, whoops 😂
great great
too good
Thanks so much!
Three sum is more interesting.
You have a loop of index i and inside you solve with this TP algorithm to find j and k
Yeah 3sum is definitely interesting with its intricacies around this and avoiding duplicates
Do these companies still ask such easy questions?
Sometimes! Nowadays they're leaning into more difficult ones though
Why n is being used to define r before it is defined
Because I'm dumb
Suggestion: Pls pause for an extra couple of seconds after revealing your soln.
Thank you. 60 second time limit so unfortunately it can get kinda rushed at the end. Sorry about that
You can pause.
It looks like a binary search what is difference between the br and tp
Not a binary search!
In BS, you're eliminating half the list with each iteration, resulting in O(logN) time.
With TP, you're still iterating through the whole list, but with 2 pointers instead of one. This results in O(N) time if you're not nesting pointer iterations.
Why return l+1 and r+1 not l and r you found?
Yeah just the stupid problem desired that for some reason
could you still use a hash map on this one?
You don’t really need hash map for this one. Try doing a dry run of this with a hashmap and you will notice right away that there is no use of it.
That would still get you a solution, but it's less efficient, and the actual problem description on Leetcode says that your solution "must use constant space", althought it doesn't enforce that. Using a hashmap would be O(n) space, not O(1)
*Ch. 1113
not 1118
Sorry?
Two sum 2 is easier than two sum 1 imo
Yes quite arguably it is
It's not an array 😭
What do you mean?
What if it’s unsorted?
Then you use normal two sum
You use two sum. Where you basically go and and get the first number add it with everything if no sum equals target then you go to de next number adding it with everything but skipping the first number
@@Progamertoatoh that would n**2 time complexity or basically we can convert that normal two sum to this one by sorting making whole complexity as nlogn.
Just thinking if we can do like AVL and work on some way to get answer in O(n)
You'd use a Hashmap and check for each number if its complement (target - itself) is in the map
@@GregHoggmake sense. That should be worst case o(nlogn) too if we assume hashmap has so much collision or we using balanced tree internally for hashmap thus eventually making it O(nlogn). Best case O(n)/ avg case O(n) definitely.
How about three sum say finding triplet a+b+c = 0. Can we do something using hashmap?
Maybe like this:
Say b+c = k.
Then find for a = -k.
We can get all combinations of b and c as nc2 or O(n^2) and then find if -k exists in hashlist of a, just that we need to keep track of not using same element of b and c.
This could be one way from two pointer but i feel using standard two pointer is much better