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.

Approach 1: Two-Pointer Technique

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        
        vector<int> ans;
        int start = 0;
        int end   = arr.size()-1;

        while(end-start+1 > k){

            int diffFromStart = abs(arr[start]-x);
            int diffFromEnd = abs(arr[end]-x);

            // If distance of x from starting point is greater than
            // ending point then move 'start' pointer else move 'end' pointer.
            if(diffFromStart>diffFromEnd)
                start++;
            else
                end--;
        }

        for(int i=start;i<=end;i++)
            ans.push_back(arr[i]);

        return ans;
    }
};

Approach 2: Max Heap

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        
        // Max Heap. Hence, farthest point will be on the top of the Heap.
        priority_queue<pair<int,int>> pq;
        vector<int> ans;

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

            int distance = abs(x-arr[i]);
            pq.push({distance,arr[i]});

            if(pq.size()>k)
                pq.pop();
        }

        while(!pq.empty()){

            ans.push_back(pq.top().second);
            pq.pop();
        }
        sort(ans.begin(),ans.end());
        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.