Find two integers in a sorted array such that a - b = k

Question

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

O(n logn) Solution:

1. Traverse the array: O(n)
2. For element a[i], find a[i]+k in the array using binary search :O(log n)

Total Time: O(n logn)

O(n) Solution:

1. Store all elements of the array in a Hash Table: O(n)
2. For element a[i], check whether a[i]+k in the hash table : O(1)

Total Time: O(n)

Space: O(n)

But he wants an O(n) solution with O(1) extraspace. Anyone have any idea?

Answer 1

Make two index pointers - Left and Right, initialize both to the start of array (0). If a[Left] + k > a[Right], increment Right, else increment Left. Stop when equal