12. K Closest Elements

โœ… GFG solution to the K Closest Elements problem: find k closest elements to target x in sorted array using binary search and two pointers. ๐Ÿš€

The problem can be found at the following link: ๐Ÿ”— Question Link

๐Ÿงฉ Problem Description

You are given a sorted array arr[] of unique integers, an integer k, and a target value x. Return exactly k elements from the array closest to x, excluding x if it exists.

An element a is closer to x than b if:

  • |a - x| < |b - x|, or

  • |a - x| == |b - x| and a > b (prefer the larger element if tied)

Return the k closest elements in order of closeness.

๐Ÿ“˜ Examples

Example 1

Input: arr[] = [1, 3, 4, 10, 12], k = 2, x = 4
Output: 3 1
Explanation: 4 is excluded. Closest elements to 4 are:
- 3 (distance = 1)
- 1 (distance = 3)
So, the 2 closest elements are: 3 1

Example 2

Input: arr[] = [12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56], k = 4, x = 35
Output: 39 30 42 45
Explanation:
- First closest: 39 (distance = 4)
- Second closest: 30 (distance = 5)
- Third closest: 42 (distance = 7)
- Fourth closest: 45 (distance = 10)

๐Ÿ”’ Constraints

  • $1 \le \text{arr.size()} \le 10^5$

  • $1 \le k \le \text{arr.size()}$

  • $1 \le x \le 10^6$

  • $1 \le \text{arr}[i] \le 10^6$

โœ… My Approach

The optimal approach uses Binary Search to find the insertion point, followed by Two Pointers technique to find the k closest elements:

Binary Search + Two Pointers

  1. Find Insertion Point:

    • Use binary search to find the largest element smaller than x.

    • This gives us the optimal starting position for two pointers.

  2. Initialize Two Pointers:

    • i = p (pointing to largest element < x)

    • j = p + 1 (pointing to smallest element โ‰ฅ x)

    • If arr[j] == x, increment j to skip the target element.

  3. Expand Outward:

    • Compare distances |arr[i] - x| and |arr[j] - x|.

    • Choose the closer element and move the corresponding pointer.

    • If distances are equal, prefer the larger element.

  4. Handle Remaining Elements:

    • If one pointer goes out of bounds, collect remaining elements from the other side.

๐Ÿ“ Time and Auxiliary Space Complexity

  • Expected Time Complexity: O(log n + k), where n is the array size. Binary search takes O(log n) and collecting k elements takes O(k).

  • Expected Auxiliary Space Complexity: O(1), as we only use constant extra space for pointers and variables (excluding the output array).

๐Ÿง‘โ€๐Ÿ’ป Code (C++)

class Solution {
  public:
    vector<int> printKClosest(vector<int> a, int k, int x) {
        int n = a.size(), l = 0, h = n - 1, p = -1;
        while (l <= h) {
            int m = (l + h) / 2;
            if (a[m] < x) p = m, l = m + 1;
            else h = m - 1;
        }
        int i = p, j = p + 1;
        if (j < n && a[j] == x) j++;
        vector<int> r;
        while (i >= 0 && j < n && r.size() < k)
            r.push_back(abs(a[i] - x) < abs(a[j] - x) ? a[i--] : a[j++]);
        while (i >= 0 && r.size() < k) r.push_back(a[i--]);
        while (j < n && r.size() < k) r.push_back(a[j++]);
        return r;
    }
};
โšก View Alternative Approaches with Code and Analysis

๐Ÿ’ก Algorithm Steps:

  1. Find the position where x would be inserted using linear search.

  2. Use two pointers to expand outward from that position.

  3. Compare distances and pick the closer element.

class Solution {
  public:
    vector<int> printKClosest(vector<int> a, int k, int x) {
        int n = a.size(), pos = 0;
        while (pos < n && a[pos] < x) pos++;
        int i = pos - 1, j = pos;
        if (j < n && a[j] == x) j++;
        vector<int> r;
        while (i >= 0 && j < n && r.size() < k)
            r.push_back(abs(a[i] - x) < abs(a[j] - x) ? a[i--] : a[j++]);
        while (i >= 0 && r.size() < k) r.push_back(a[i--]);
        while (j < n && r.size() < k) r.push_back(a[j++]);
        return r;
    }
};

๐Ÿ“ Complexity Analysis:

  • Time: โฑ๏ธ O(n + k)

  • Auxiliary Space: ๐Ÿ’พ O(1)

โœ… Why This Approach?

  • Simple linear search approach.

  • Good when array size is small or unsorted.

๐Ÿ“Š 3๏ธโƒฃ Priority Queue (Min Heap)

๐Ÿ’ก Algorithm Steps:

  1. Create a min-heap with custom comparator based on distance from x.

  2. Add all elements except x to the heap.

  3. Extract k smallest elements from the heap.

class Solution {
  public:
    vector<int> printKClosest(vector<int> a, int k, int x) {
        auto cmp = [x](int a, int b) {
            int distA = abs(a - x), distB = abs(b - x);
            return distA == distB ? a < b : distA > distB;
        };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        for (int num : a) {
            if (num != x) pq.push(num);
        }
        vector<int> r;
        while (r.size() < k && !pq.empty()) {
            r.push_back(pq.top());
            pq.pop();
        }
        return r;
    }
};

๐Ÿ“ Complexity Analysis:

  • Time: โฑ๏ธ O(n log n + k log n)

  • Auxiliary Space: ๐Ÿ’พ O(n)

โœ… Why This Approach?

  • Handles unsorted arrays naturally.

  • Good for small k values.

๐Ÿ†š ๐Ÿ” Comparison of Approaches

๐Ÿš€ Approach

โฑ๏ธ Time Complexity

๐Ÿ’พ Space Complexity

โœ… Pros

โš ๏ธ Cons

๐Ÿ” Binary Search

๐ŸŸข O(log n + k)

๐ŸŸข O(1)

โšก Fastest for sorted arrays

๐Ÿงฎ Requires sorted input

๐Ÿ”„ Linear Search

๐ŸŸก O(n + k)

๐ŸŸข O(1)

๐Ÿ”ง Simple, works with unsorted

๐Ÿข Slower for large arrays

๐Ÿ“ฆ Priority Queue

๐Ÿ”ธ O(n log n + k log n)

๐Ÿ”ธ O(n)

๐Ÿช„ Natural ordering by distance

๐Ÿšซ High time and space complexity

๐Ÿ† Best Choice Recommendation

๐ŸŽฏ Scenario

๐ŸŽ–๏ธ Recommended Approach

๐Ÿ”ฅ Performance Rating

โšก Large sorted array, performance critical

๐Ÿฅ‡ Binary Search

โ˜…โ˜…โ˜…โ˜…โ˜…

๐Ÿ”ง Small array, simplicity preferred

๐Ÿฅˆ Linear Search

โ˜…โ˜…โ˜…โ˜…โ˜†

๐Ÿ“Š Need flexible distance-based ordering

๐Ÿฅ‰ Priority Queue

โ˜…โ˜…โ˜…โ˜†โ˜†

๐Ÿง‘โ€๐Ÿ’ป Code (Java)

class Solution {
    int[] printKClosest(int[] a, int k, int x) {
        int n = a.length, l = 0, h = n - 1, p = -1;
        while (l <= h) {
            int m = (l + h) / 2;
            if (a[m] < x) { p = m; l = m + 1; }
            else h = m - 1;
        }
        int i = p, j = p + 1;
        if (j < n && a[j] == x) j++;
        int[] r = new int[k]; int idx = 0;
        while (i >= 0 && j < n && idx < k)
            r[idx++] = Math.abs(a[i] - x) < Math.abs(a[j] - x) ? a[i--] : a[j++];
        while (i >= 0 && idx < k) r[idx++] = a[i--];
        while (j < n && idx < k) r[idx++] = a[j++];
        return r;
    }
}

๐Ÿ Code (Python)

class Solution:
    def printKClosest(self, a, k, x):
        n, l, h, p = len(a), 0, len(a) - 1, -1
        while l <= h:
            m = (l + h) // 2
            if a[m] < x: p = m; l = m + 1
            else: h = m - 1
        i, j, r = p, p + 1, []
        if j < n and a[j] == x: j += 1
        while i >= 0 and j < n and len(r) < k:
            r.append(a[i] if abs(a[i] - x) < abs(a[j] - x) else a[j])
            if abs(a[i] - x) < abs(a[j] - x): i -= 1
            else: j += 1
        while i >= 0 and len(r) < k: r.append(a[i]); i -= 1
        while j < n and len(r) < k: r.append(a[j]); j += 1
        return r

๐Ÿง  Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: ๐Ÿ“ฌ Any Questions?. Let's make this learning journey more collaborative!

โญ If you find this helpful, please give this repository a star! โญ


๐Ÿ“Visitor Count

Visitor counter

Last updated