Find K Closest Elements
Ramayana — The Ring of Allies — k Warriors Closest in Strength to Rama
k निकटतम तत्व — क्रमबद्ध सरणी में। बाएं सीमा ढूंढो — x से दूरी न्यूनतम॥
*k closest elements — in a sorted array. Find the left boundary — minimum distance from x.*
The Story
Given a sorted array and values k and x, find the k closest integers to x. If two numbers are equally close, prefer the smaller one.
For `arr=[1,2,3,4,5]`, k=4, x=3: answer=[1,2,3,4].
The k closest elements form a contiguous window of size k in the sorted array.
**Binary Search to find left boundary:** We want to find the starting index `left` of the optimal window [left, left+k-1]. - Compare `arr[mid]` and `arr[mid+k]` by distance to x - If `x - arr[mid] > arr[mid+k] - x`: the window starting at mid is worse than starting at mid+1 → `left = mid+1` - Otherwise: `left = right = mid` (don't push right past current)
```java int left=0, right=arr.length-k; while (left < right) { int mid = (left+right)/2; if (x - arr[mid] > arr[mid+k] - x) left=mid+1; else right=mid; } // Window is arr[left..left+k-1] ```
Why does this work? We're comparing the leftmost and rightmost candidates: - `arr[mid]` = potential leftmost of window - `arr[mid+k]` = element just outside the right of a window starting at mid - If mid+k is closer to x than mid, shift the window right
Trace `[1,2,3,4,5]`, k=4, x=3: - left=0, right=1 - mid=0: x-arr[0]=3-1=2, arr[4]-x=5-3=2. 2>2? No → right=0 - left==right=0 → window [0..3] = [1,2,3,4] ✓
The Sort-by-Distance Approach
Sort by |x-arr[i]| (then by value for ties). Take first k. Sort the k elements. O(n log n).
public List<Integer> findClosestElementsBruteForce(int[] arr, int k, int x) {
List<Integer> list = new ArrayList<>();
for (int v : arr) list.add(v);
list.sort((a,b)->Math.abs(a-x)!=Math.abs(b-x)?
Math.abs(a-x)-Math.abs(b-x):a-b);
list = list.subList(0,k);
Collections.sort(list);
return list;
}The Window-Left-Boundary Binary Search
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int left = 0, right = arr.length - k;
while (left < right) {
int mid = left + (right - left) / 2;
if (x - arr[mid] > arr[mid + k] - x) left = mid + 1;
else right = mid;
}
List<Integer> result = new ArrayList<>();
for (int i = left; i < left + k; i++) result.add(arr[i]);
return result;
}Step-by-Step Walkthrough
[1,3,3,3,5], k=3, x=3 right=2 mid=1: 3-3=0, 3-3=0. 0>0? No→right=1 mid=0: 3-1=2, 3-3=0. 2>0→left=1 left==right=1→[3,3,3] ✓
Deep Insight
**Why compare arr[mid] and arr[mid+k] (not arr[mid+k-1])?** A window of size k starting at mid occupies [mid..mid+k-1]. The element just OUTSIDE the right is arr[mid+k]. We compare the leftmost element of the window (arr[mid]) with the first element that would join if we shifted right (arr[mid+k]). This is the key boundary comparison.
**The `>=` direction:** `x - arr[mid] > arr[mid+k] - x` means arr[mid+k] is strictly closer to x than arr[mid]. If equal distance (equal), we prefer arr[mid] (smaller value) → keep right = mid (don't push right).
**O(log(n-k) + k):** Binary search on range [0, n-k] → O(log(n-k)). Then collect k elements → O(k).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(n) | Sort by distance |
| Optimal | O(log(n-k) + k) | O(1) | Binary search for window start + O(k) to collect |
Pattern Recognition
✅ k closest in sorted array → find left boundary of window ✅ Compare arr[mid] vs arr[mid+k] distance to x ✅ right = arr.length - k (valid starting positions) ✅ Equal distance → prefer smaller (right=mid, not left=mid+1) **LeetCode Trigger Phrases:** → "find k closest elements" in sorted array → Contiguous window of k elements closest to x → Binary search for optimal window left boundary
Bhagavad Gita 6.9
सुहृन्मित्रार्युदासीनमध्यस्थद्वेष्यबन्धुषु। साधुष्वपि च पापेषु समबुद्धिर्विशिष्यते॥
One who regards with equal mind the well-wisher and friend, the enemy and the indifferent, the mediator and the hateful, the relative and both the pious and the sinful — is distinguished.
Connection: The algorithm seeks those closest to x — the most aligned with a given value. By binary searching for the optimal window, it finds exactly the k elements whose proximity to x is greatest. The comparison between the leftmost and rightmost candidates of each potential window mirrors the process of discernment: which extreme is closer to the ideal? The chosen window holds those with the most equanimity relative to x, just as the equanimous sage holds those most aligned with balanced wisdom.