Question

Write three different algorithms of different time complexities to find the closest pair in a sorted array of integers. (Using java)

Answer 1

1. Naive algorithm

public static void closestPair(int[] Arr, int sum)
   {
       for (int i = 0; i < Arr.length - 1; i++)
       {           for (int j = i + 1; j < Arr.length; j++)
           {
               if (Arr[i] + Arr[j] == sum)
               {
                   System.out.println("Pair found at index " + i + " and " + j);
                   return;
               }
           }
       }
       System.out.println("Pair not found");
   }

Time complexity: O(n²)

2. nlogn algorithm

public static void closestPair(int[] Arr, int sum)
   {
       int low = 0;
       int high = Arr.length - 1;
       while (low < high)
       {
           if (Arr[low] + A[high] == sum)
           {
               System.out.println("Closest Pair found");
               return;
           }

           if (Arr[low] + Arr[high] < sum) {
               low++;
           } else{
               high--;
           }
       }

       System.out.println("Closest Pair not found");
   }

Time complexity: O(nlogn)

3. O(n) algorithm using hashing

import java.util.HashMap;
import java.util.Map;
class Main
{
   public static void closestPair(int[] Arr, int sum)
   {
       Map<Integer, Integer> map = new HashMap<>();
       for (int i = 0; i < Arr.length; i++)
       {

           if (map.containsKey(sum - Arr[i]))
           {
               System.out.println("Closest Pair found at index " +
                               map.get(sum - Arr[i]) + " and " + i);
               return;
           }

           map.put(Arr[i], i);
       }

       System.out.println("Closest Pair not found");
   }

}

Time complexity: O(n)