27 Apr 2014

Arrays: K Closest ELements

Problem Statement:
       Given a number in a sorted array , find K closest elements to that number.


Closest Integers in the vicinity of 8 are : 5,6,7,10

Solution: 
Run Source Code

     Since the given array is sorted , binary search can be applied to get the index of the given number.
We will then place two pointers viz left and right , which will decremented and incremented respectively based on the minimum difference with the given number.

Below is the logic implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
     public static int[] KClosestElements(int[] arr, int index, int k){
  int left = index -1;
  int right = index +1;
  int[] result = new int[k];

  while(right - left -2 < k )
  {
   if(arr[right] - arr[index] > arr[index]- arr[left])
   {
    if(left>0)
     result[right - left - 2] = arr[left--];
    else 
     result[right - left - 2]=arr[right++];
   }
   else
   {
    if(right < arr.length)
     result[right - left - 2]=arr[right++];
    else
     result[right - left - 2] = arr[left--];
   }
   
   //result[right - left] = arr[right] - arr[index] > arr[index]- arr[left] ?  if(left>0){arr[left--]} : arr[right++] ;
  }
  System.out.println(Arrays.toString(result));
  
  return result;
 }

Binary Search Sub-routine


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
       private static int binarySearch(int[]arr,int num,int low,int high) {
  while(low<=high)
  {
   int mid=(low+high)/2;
   if(arr[mid]==num)   return mid;
   else if(arr[mid] < num)  low=mid+1;
   else if (arr[mid] > num) high=mid-1;
  }
  return -1;
 }

Please post comments and suggestions.
Happy Coding !! :)

No comments:

Post a Comment