Find K Closest Elements

LeetCode 658 | Difficulty: Medium

Medium

Problem Description

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| arr = [1,2,3,4,5], k = 4, x = 3

Output: [1,2,3,4]

Example 2:

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

Output: [1,1,2,3]

Constraints:

- `1 <= k <= arr.length`

- `1 <= arr.length <= 10^4`

- `arr` is sorted in **ascending** order.

- `-10^4 <= arr[i], x <= 10^4`

Topics: Array, Two Pointers, Binary Search, Sliding Window, Sorting, Heap (Priority Queue)

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 188 ms)

Metric	Value
Runtime	188 ms
Memory	48.9 MB
Date	2022-02-05

Solution

public class Solution {
    public IList<int> FindClosestElements(int[] arr, int k, int x) {
        int lo = 0, hi = arr.Length - k;
    while (lo<hi)
    {
        int mid = (lo+hi)/2;
        if (x - arr[mid] > arr[mid+k] - x)
        {
            lo=mid+1;
        }
        else hi = mid;;
    }
    IList<int> result = new List<int>();
    for (int i = lo; i < lo+k; i++)
    {
        result.Add(arr[i]);
    }
    return result;
    }
}

📜 1 more C# submission(s)

Submission (2022-02-05) — 300 ms, 47.2 MB

public class Solution {
    public IList<int> FindClosestElements(int[] arr, int k, int x) {
        int lo = 0, hi = arr.Length-1;
    while(hi-lo>=k)
    {
        if(Math.Abs(x-arr[lo])>Math.Abs(arr[hi]-x))
        {
            lo++;
        }
        else hi--;
    }
    IList<int> result = new List<int>();
    for (int i = lo; i <= hi; i++)
    {
        result.Add(arr[i]);
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Binary Search	$O(log n)$	$O(1)$
Sliding Window	$O(n)$	$O(k)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Precisely define what the left and right boundaries represent, and the loop invariant.