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
andj> J
we are not going to find our solution becauseA[j]
will be increasing(Array is sorted) so willA[j]-A[I]
.when
i
increase thenA[i]
will increase too thenA[J]- A[i]
will decrease so tillj =J-1
ourA[j] -A[i]
will be less thanDiff_1
which is also less thank
( Observation 1 ) So we will not find our solution tillj =J-1
. So Efficient Approach will be when we don’t startj
every time withI+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)