Find K Closest Elements - Practice Coding Problems

Find K Closest Elements - Problem

Array Two Pointers Binary Search Sliding Window Sorting Heap (Priority Queue) Medium

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

Input & Output

Example 1 — Basic Case

$ Input: arr = [1,2,3,4,5], k = 4, x = 3

› Output: [1,2,3,4]

💡 Note: The 4 closest elements to 3 are [1,2,3,4]. Distances: |1-3|=2, |2-3|=1, |3-3|=0, |4-3|=1, |5-3|=2. Elements 2,3,4 have distances 1,0,1 respectively, and 1 has distance 2, so we take [1,2,3,4].

Example 2 — Target Not in Array

$ Input: arr = [1,2,3,4,5], k = 4, x = -1

› Output: [1,2,3,4]

💡 Note: The 4 closest elements to -1 are the first 4 elements. Distances: |1-(-1)|=2, |2-(-1)|=3, |3-(-1)|=4, |4-(-1)|=5, |5-(-1)|=6. The smallest 4 distances correspond to elements [1,2,3,4].

Example 3 — Tie Breaking

$ Input: arr = [1,1,1,10,10,10], k = 1, x = 9

› Output: [10]

💡 Note: Both 1 and 10 have distance |1-9|=8 and |10-9|=1 respectively to x=9. Since |10-9|=1 < |1-9|=8, we choose 10.

Constraints

1 ≤ k ≤ arr.length
1 ≤ arr.length ≤ 10⁴
-10⁴ ≤ arr[i], x ≤ 10⁴
arr is sorted in ascending order

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array [1,2,3,4,5], k=4, x=3

Process

Find elements with minimum distance to x=3

Output

Return [1,2,3,4] in sorted order

Key Takeaway

🎯 Key Insight: Use binary search to find target position, then expand with two pointers for optimal O(log n + k) solution

Asked in

a Amazon 45 G Google 35 f Facebook 28 M Microsoft 22

The key insight is to leverage the sorted property of the array. We can use binary search to find x's position in O(log n), then expand a window with two pointers to get the k closest elements in O(k) time. Best approach is Two Pointers with Binary Search: Time O(log n + k), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Sorting	O(n log n)	O(n)	Calculate distances for all elements, sort by distance, take first k
Two Pointers with Binary Search	O(log n + k)	O(1)	Find x's position with binary search, then expand window with two pointers
Sliding Window Approach	O(n)	O(1)	Find optimal window of size k by removing elements that are farther

Brute Force with Sorting — Algorithm Steps

Step 1: Calculate |arr[i] - x| for each element
Step 2: Sort elements by distance, then by value for ties
Step 3: Take first k elements and sort result

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Distances

Find |arr[i] - x| for each element

Sort by Distance

Sort (distance, value) pairs

Take First K

Extract first k values and sort result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int dist;
    int val;
} Pair;

int compare(const void* a, const void* b) {
    Pair* pa = (Pair*)a;
    Pair* pb = (Pair*)b;
    if (pa->dist != pb->dist) {
        return pa->dist - pb->dist;
    }
    return pa->val - pb->val;
}

int compareInt(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* arr, int arrSize, int k, int x, int* returnSize) {
    // Calculate distances and create pairs
    Pair* distances = (Pair*)malloc(arrSize * sizeof(Pair));
    for (int i = 0; i < arrSize; i++) {
        int dist = abs(arr[i] - x);
        distances[i].dist = dist;
        distances[i].val = arr[i];
    }
    
    // Sort by distance, then by value for ties
    qsort(distances, arrSize, sizeof(Pair), compare);
    
    // Extract first k values
    int* result = (int*)malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        result[i] = distances[i].val;
    }
    
    // Sort result in ascending order
    qsort(result, k, sizeof(int), compareInt);
    
    free(distances);
    *returnSize = k;
    return result;
}

int main() {
    // Parse input array
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int arrSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL && arrSize < 1000) {
        arr[arrSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k, x;
    scanf("%d", &k);
    scanf("%d", &x);
    
    int returnSize;
    int* result = solution(arr, arrSize, k, x, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting all n elements by their distances

⚡ Linearithmic

Space Complexity

O(n)

Extra array to store (distance, value) pairs

⚡ Linearithmic Space

125.0K Views

High Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler