Hi Devs, Happy Coding

I am planning to revise Data Structure and Algorithms Concepts so I will be sharing my approach as well as a full solution for problems I solve. This is my first attempt at writing a dev blog, yeah I am a bit nervous. Hope you like it and Your valuable feedback and contributions are always welcome.

Today I am going to solve a coding problem Diffk which is based on the Two Pointer concept.

**Asked In - Facebook Interview**

Problem Statement - Given an array ‘A’ of sorted integers and another non negative integer k, find if there exists 2 indices i and j such that A[i] - A[j] = k, i != j.

**Time and Space Complexity Constraint**

1. Try doing this in less than linear space complexity.

**Example**

```
Input :
A : [1 3 5]
k : 4
Output : YES
Explanation : as 5 - 1 = 4
```

**Brute Force Approach -** we use two loop for two indices i,j and iterate if we find any A[j]-A[i] = k and i!=j then return 1 else 0.

```
int diffPossible(vector<int> &A, int k) {
int N= A.size();
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (A[j] - A[i] > k) break; // No need check forward because Array is sorted so the difference is going to increase even further because A[I] is going to increase or remain same.
if (A[j] - A[i] == k) return 1;
}
}
return 0;
}
```

The Time Complexity of this approach is O(N*N).

**Observation**

Let's check the above approach when we have `i = I`

and find `j=J`

,`Diff_1 =(A[J-1]-A[I])`

such that `Diff_1 <k`

and `A[J]-A[I] >k`

This means that for

`i =I`

and`j> J`

we are not going to find our solution because`A[j]`

will be increasing(Array is sorted) so will`A[j]-A[I]`

.when

`i`

increase then`A[i]`

will increase too then`A[J]- A[i]`

will decrease so till`j =J-1`

our`A[j] -A[i]`

will be less than`Diff_1`

which is also less than`k`

( Observation 1 ) So we will not find our solution till`j =J-1`

. So Efficient Approach will be when we don’t start`j`

every time with`I+1`

but start with j=J.

**New Approach Code (Time Complexity: O(n))**

```
int diffPossible(vector<int> &A, int k) {
int N = A.size();
int j = 0;
for (int i = 0; i < N; i++) {
j = max(j, i+1);
while (j < N && (A[j] - A[i] < B)) {
j += 1;
}
if (A[j] - A[i] == B) return 1;
}
return 0;
}
```

## Top comments (0)