Find Pair with given Difference | GFG Solution | Searching and Sorting

[animationcity]

Ma'am kafi dino se try kar raha tha solve nahi ho raha tha but ab samjh agaya 😀

[ridimamittal]

The TLDR is to not put i = 0, and j = N-1 as we will lose the correct answer for when B is -ve.
Instead, initialize i and j to the start of the array and let the difference in value btw this value and B decide the next positions of i and j. If B is -ve, i will take over j and diff will inc. in -ve value. If B is +ve, the j value first increases and then after a point the i value increases.

[codebits]

Your explanation always outstanding 👏👏

[gianthub]

For those who are getting wrong output
if key is 0 on array
arr = 1 2 6 3 4;
class Solution {
public boolean findPair(int arr[], int size, int target) {
Arrays.sort(arr);
int i = 0;
int j = 1;

while (j < size) {
int diff = arr[j] - arr[i];
if (diff == target) {
if (i != j) {
return true;
}
j++; // Move j forward since i == j is not a valid pair
} else if (diff < target) {
j++;
} else {
i++;
}
}

return false;
}
}

[pranavkorhale]

First sort the array
if(n==0)
{
while(j<arr.length)
{
if(arr[i]==arr[j])
{
return true;
}
i++;j++;
}
}else{
/*Manisha mam code from line no 13 to 24 */
}


By this it will work for target 0 as well

[crackthecode]

Arrays.sort(arr);
int lo=0;
int hi=arr.length-1;
while(lo<=hi){
if(arr[lo]+n==arr[hi]){
return true;
}else if(arr[lo]+n<arr[hi]){
lo++;
}else{
hi--;
}
}
return false;

whats wrong in this approach?? here n is the target, i have sorted my array and since x-y=target so x=target+y i m just looking for pairs that satisfy this relation in array.

[mohammadabuzaid]

arr[ ]={1, 2, 3, 4, 6}, target = 0
why this code gives the wrong output for the above test case.

[riyashetye]

how to find those pairs whose difference is same as the their indices difference. but time complexity less then n^2

[mickyman]

hashset se O(n) se ho jaega but extra space lgegi hashset ki

[ravisingh-elnp]

// b can be negative also
// int Solution::solve(vector<int> &A, int B) {
// sort(A.begin(), A.end());
// int i=0, j=1, n=A.size();
// while(i < n && j<n)
// {
// int diff= A[j] -A[i];
// if(diff == B)
// return 1;
// else if(diff>B)
// {
// i++;
// if(i==j)
// i++;
// }
// else {
// j++;
// if(i==j)
// j++;
// }
// }
// return 0;
// }

[gmmkeshav]

why cannot we use maps?

but when we use maps
we can have examples like 4, 4, 4, 4
and suppose k is 0
then answer should be 6

[yashyadav]

didi its not working when key =0
arr = 1 2 6 3 4;
i am getting wrong ans

[aakashsharma]

Great approach mam but plss may u tell me the time complexity of this code.

[devangpathak]

sort(arr, arr+size);
int i = 0;
int j = 1;

// Search for a pair
while (i < size && j < size)
{
if ((i != j) && (arr[j] - arr[i] == n || arr[i] - arr[j] == n) )
{
return true;
}
else if (arr[j]-arr[i] < n)
j++;
else
i++;
}

return false;

[gauravsoni]

here
for 5 0
1 2 3 4 5
this code will give a wrong answer coz same index par it will give 0 diffrence and true output which does not exist