## DEV Community # Diffk Solution - Interviewbit

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.

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;
}
``````