Find K Closest Elements

Thought Process

The challenge is to efficiently locate K closest elements to 'x' in a sorted array while maintaining optimal performance. Here are two efficient approaches:

Approach 1: Two-Pointer Technique - Use two pointers, start and end, at the array's boundaries. Calculate absolute differences from 'x' for both pointers. Move the pointer with the larger difference inward until the window contains exactly K elements.

Approach 2: Max Heap - Use a max heap to maintain the K closest elements. For each element, calculate its distance from 'x' and push it into the heap. If the heap size exceeds K, remove the top element of the heap. Finally, sort the results for the required order.

class Solution {

    public List<Integer> findClosestElements(int[] arr, int k, int x) {

        List<Integer> ans = new ArrayList<>();
        int start = 0;
        int end = arr.length-1;

        while(end-start+1>k){

            int diffStart = Math.abs(arr[start]-x);
            int diffEnd = Math.abs(arr[end]-x);

            if(diffStart > diffEnd)
                start++;
            else
                end--;
        }
        for(int i=start;i<=end;i++)
            ans.add(arr[i]);

        return ans;
    }
}

class Solution {

    public List<Integer> findClosestElements(int[] arr, int k, int x) {

        // Max Heap. 
        // Hence, farthest point will be on the top of the Heap.
        // When two points are at same distance, then farther point will
        // be on the top of the Heap.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {

            if (a[0] == b[0])
                return (b[1] - a[1]);
            else
                return (b[0] - a[0]);
        });
        List<Integer> ans = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {

            int dist = Math.abs(arr[i] - x);
            pq.offer(new int[] { dist, arr[i] });

            if (pq.size() > k) {
                pq.poll();
            }
        }
        // Now, remaining points in the heap will be the closest one
        // & their count will be k.
        while (!pq.isEmpty()) {
            ans.add(pq.poll()[1]);
        }

        Collections.sort(ans);
        return ans;
    }
}

Code Complexity

Time Complexity: O(n) vs O(n log k)

The two-pointer approach runs in O(n) time, while the heap approach takes O(n log k) due to heap operations.

Space Complexity: O(1) vs O(k)

The two-pointer technique uses constant space, while the heap approach requires O(k) space for storage.

Java: Find K Closest Elements

Thought Process

Code Complexity

Time Complexity: O(n) vs O(n log k)

Space Complexity: O(1) vs O(k)