Two pointers in sorted array | Leetcode 167

#coding #leetcode #python #javascript Leetcode 167. Two Sum II - Input Array Is Sorted

[Fede_uyz]

You do have to start with a sorted list however, but a clever solution!

[RakeshSingh-vlmz]

Thanks brother
U are helping revising DSA in a consistent manner

[brokegod]

This is the infamous Two Sum problem

1) Either use brute force to generate all pairs and just break out whenever you find a match to the target

2) Prefix sum + hashing is an optimised solution if you wanna use extra space, the equation is Target = A + B so we're gonna check if Target - A (which is B) exists in the hash while we keep doing prefix sum, if it exists we can break out

3) Two Pointer on SORTED array, just min maxing whenever the sum goes above or below the target

Two pointer won't work if they ask for the exact index of the elements of the pair as you'll end up sorting, in that case prefix sum + hashing would help where you can store a pair in the hash as prefix sum and index

[dineshkumare]

I thought of checking whether arr [ i ] - target is in the arr.Since the array is sorted we can use binary search the element. But this will take nlogn time. The Two pointer technique is elegant.!!

[spicyshizz]

I was thinking of doing a binary search for 9 and and then starting the right number that’s in the list right below 9. However I’d have to account for two cases, there is no 9 in the list and negative numbers…

[Germisstucklmao]

I was thinking to just use 2 variables which store the values, but that works too

[mahasinirfan]

If you have an array like [1, 2, 3, 7, 8, 10] with the target 9, then doesn't this method fail? the left ptr would increment and right would decrement, they would never point to 2 and 7 simultaneously hence not reaching the target

[mangto]

Do you know that the hat you're wearing has "Soon to be Rich(곧갑부)" written in Korean? I love that hat!

[htfuh]

not gonna finish watching this is my own solution, take the number and subtract by the highest number and keep doing so when a solution that’s above 0 has been achieved (if zero is not already a variable if so then if equal to zero) use that number and check if it’s in the list if so place the first and second together. Bam not saying this is the best just an attempt of my own any thought would be cool

[williampatrick]

And the second pointer should not be higher than the target

[_WaffleEater_]

couldn't you subtract the target by all of the numbers on the list, e.g, 9-7=2 so, therefore 9=7+2 so thats the answer, your strategy might be more useful if you had, say 100 numbers, but on a small modal like this, its just easier to subtratct

[sammyfromsydney]

The older and more experienced I get as a developer the more I understand how worthless knowing canned answers for convoluted problems are. Almost no one watching this video will ever have need for this algorithm, and if by some miracle someone is working on a problem that requires this somehow they should have the time to research prior solutions and try their own. Companies and senior developers need to find better ways to filter their candidates.

[СергейДехтярёв-ън]

#include <stdio.h>

int get_sum_for_target(int *array, int length, int target, int *a, int *b)
{
int left = 0;
int right = length - 1;

if (left == right) return 1;

while (left < right) {
int sum = array[left] + array[right];

if (sum == target) {
*a = array[left];
*b = array[right];
return 0;
}

if (sum > target) {
right--;
continue;
}

left++;
}

return 0;
}

int main()
{
int arr[5] = {1, 2, 3, 4, 5};
int target = 4;
int a = -1;
int b = -1;
if (get_sum_for_target(
arr, 5, target, &a, &b) == 1) {
printf("not found\n");
return 1;
}
printf("%d, %d\n", a, b);

return 0;
}

That actually works, cool