45. Find K Closest Elements

Topic :

binary search

Difficulty :

medium

Problem Link :

problem statement

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Constraints:

1 <= k <= arr.length
1 <= arr.length <= 104
arr is sorted in ascending order.
-104 <= arr[i], x <= 104

solution

TIME COMPLEXITY : O( logN + klogk)

SPACE COMPLEXITY : O(1)

import java.io.*;
import java.util.*;
class Find_K_Closest_Elements {
    public static void main(String args[])
    {
      int arr[]={10,20,30,40,50,60};
      int x=45;
      int k=4;
      System.out.println(findClosestElements(arr,k,x));
    }
    static List<Integer> findClosestElements(int[] arr, int k, int x) {
        int low=0;
        int high=arr.length-1;
        int mid=0;
        
        // use binary search to find the element closest to x
        while(low<=high)
        {
            mid=(low+high)/2;
            if(arr[mid]==x){
                break;
            }
            else if(arr[mid]<x){
                low=mid+1;
            }
            else{
                high=mid-1;
            }
        }
        // the position of element closest to x is in mid now
        int left=-1;
        int right=-1;
       
        // handling edge cases
        if(mid>0){
          left=mid-1;
          right=mid;  
        }
        else
        {
            left=mid;
            right=mid+1;
        }
         
        
        List<Integer> ans=new ArrayList<Integer>();
        
        // search for the k closest elements in the left and right half
        while(left>=0 && right <arr.length && k>0)
        {
            if( Math.abs(arr[left]-x) <= Math.abs(arr[right]-x) ){
                ans.add(arr[left]);
                left--;
                k--;
            }
            else{
                ans.add(arr[right]);
                right++;
                k--; 
            }
        }
       
        // if we have crossed our right boundary but k is still not 0
        // we need to add elements from the left half
        while(k>0 && left>=0){
            ans.add(arr[left]);
            left--;
            k--;           
        }
        // if we have crossed our left boundary but k is still not 0
        // we need to add elements from the right half
        while(k>0 && right<arr.length){
            ans.add(arr[right]);
            right++;
            k--; 
        }
        
        // sort the ans
        Collections.sort(ans);
        return ans;
    }
}