Constant Boundary Separation

Given an integer k and an sorted array A (can consist of both positive and negative numbers), output 2 integers from A such that a-b=k in O(n) time and O(1) space.

Solution

Idea is to take two indices i and j which initially point to the last element.Then

• If their difference is equal to K ,then output the required answer.
• If it is less than K , then only possible way is decreasing i , 
• If it is greater than K , then only possible way is decreasing j.

Code
int boundary(int array[], int N, int K, int *a, int *b){

int i = j = N -1;
while(i >= 0 && j < N && i <= j){

if(array[j] - array[i] == K){

*a = array[j];
*b = array[i];

return 1;

}
else if(array[j] = array[i] > K)

j--;

else

i--;

}
return 0;

}

Complexity

• Time : O(N)
• Space : O(1)