Question

An abs-sorted array is an array of numbers in which |A[i]| <= |A[j]| whenever i < j.

For example, the array A = [-49, 75, 103, -147, 164, -197, -238, 314, 348, -422],

though not sorted in the standard sense, is abs-sorted. Design an algorithm that

takes an abs-sorted array A and a number k, and returns a pair of indices of elements

in A that sum up to k. For example if k = 167 your algorithm should output (3, 7).

Output (-1, -1) if the is no such pair.

Answer 1

A simple solution is to traverse each element and check if there’s another number in the array which can be added to it to give sum. But it's complexity will be O(n^2)
// Consider all possible pairs and check if theor sum = k
String pair = '';
for (int i = 0; i < arr.length; i++)
for (int j = i + 1; j < arr.length; j++)
if ((arr[i] + arr[j]) == sum){
   pair = "(" + i + "," + j + ")";
return pair;   
}

TO solve in O(n) -
Concept used -
   a + b = k
   a = b - k

for every element 'a' taken from the array, check if it already exist in the map.
   If it does not exist,
       store the map with the pair (index, k-a)
   If it already exists,
       print it's index and the index of the number already present in the map.

Pseudo code :
HashMap<Integer, Integer> map = new HashMap<>();
for (int i=0; i<n; i++){
   if(!map.containsKey(A[i]))
System.out.println("(" + i + "," + map.get(A[i]) + ")");
else
map.put(A[i],i);
}