> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find K Closest Elements Python Solution

> Tested Python solution for LeetCode 658 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 658, Medium. Topics: Array, Two Pointers, Binary Search, Sliding Window, Sorting, Heap (Priority Queue). [View on LeetCode](https://leetcode.com/problems/find-k-closest-elements/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 658   # by problem number
lcpy gen -s find_k_closest_elements   # by problem name
```

## Problem

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`

### Examples

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

```
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`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_k_closest_elements/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_k_closest_elements/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(log(n-k))
    # Space: O(1)
    def find_closest_elements(self, arr: list[int], k: int, x: int) -> list[int]:
        """
        Find k closest elements to x using binary search on window positions.

        Time: O(log(n-k)) - Binary search on n-k possible window positions
        Space: O(1) - Only using constant extra variables

        Algorithm:
        - Search space: all possible left boundaries for k-element window [0, n-k]
        - For each position mid, compare window boundaries: arr[mid] vs arr[mid+k]
        - If arr[mid] farther from x, move search right; otherwise move left
        - Leverages sorted array property for O(log) efficiency vs O(n) linear scan

        Example: arr=[0,1,2,3,4], k=3, x=3
        Windows: [0,1,2], [1,2,3], [2,3,4]
        Distances: max(2,1), max(0,1), max(1,1) → choose [1,2,3]
        """
        # Binary search to find the left boundary of the k-element window
        left, right = 0, len(arr) - k

        while left < right:
            mid = (left + right) // 2
            # Compare distances: arr[mid] vs arr[mid + k]
            # If arr[mid] is farther from x than arr[mid + k], move left boundary right
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid

        return arr[left : left + k]
```

## Complexity

| Time        | Space |
| ----------- | ----- |
| O(log(n-k)) | O(1)  |

## Tags

[Grind](/catalog/grind), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).