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|
anda > 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
Find Insertion Point:
Use binary search to find the largest element smaller than
x
.This gives us the optimal starting position for two pointers.
Initialize Two Pointers:
i = p
(pointing to largest element < x)j = p + 1
(pointing to smallest element โฅ x)If
arr[j] == x
, incrementj
to skip the target element.
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.
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;
}
};
๐งโ๐ป 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
Last updated