Find K Closest Elements

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

Example 1:

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

Output: [1,2,3,4]

Example 2:

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

Output: [1,1,2,3]

# K Closest Elements

## 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| < |b - x|`, or
*   `|a - x| == |b - x|` and `a < b`

## Naive Solution

The naive solution involves iterating through the entire array, calculating the absolute difference between each element and `x`, and storing these differences along with the elements in a list of pairs. Then, sort this list based on the differences (and element value for tie-breaking). Finally, select the first `k` elements from the sorted list. This will have a time complexity of O(n log n) due to sorting.

```python
def find_k_closest_naive(arr, k, x):
    diffs = []
    for num in arr:
        diffs.append((abs(num - x), num))

    diffs.sort(key=lambda p: (p[0], p[1]))
    
    result = [p[1] for p in diffs[:k]]
    result.sort()
    return result

Optimal Solution (Binary Search)

Since the array is sorted, we can use binary search to find the element in the array closest to x. Once we have found that closest element index, we can expand k elements to the left and right of that index. However, this approach might lead to out-of-bounds issues.

Alternatively, a better approach is to use binary search to find the leftmost index such that the subarray arr[left:left+k] contains the k closest elements to x. The logic is as follows:

1. Initialize left = 0 and right = len(arr) - k.
2. Perform binary search while left < right.
3. In the binary search, calculate mid = (left + right) // 2.
4. Compare the distance between x and arr[mid] and the distance between x and arr[mid + k].
   • If x - arr[mid] > arr[mid + k] - x, it means arr[mid] is farther from x than arr[mid + k]. This implies that the k closest elements lie to the right of mid, so update left = mid + 1.
   • Otherwise, the k closest elements are to the left or contain mid, so update right = mid.
5. The loop terminates when left == right. At this point, left is the starting index of the k closest elements.

def find_k_closest(arr, k, x):
    left = 0
    right = len(arr) - k

    while left < right:
        mid = (left + right) // 2
        if x - arr[mid] > arr[mid + k] - x:
            left = mid + 1
        else:
            right = mid

    return arr[left:left + k]

Example

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

result = find_k_closest(arr, k, x)
print(result)  # Output: [1, 2, 3, 4]

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

result = find_k_closest(arr, k, x)
print(result) # Output: [1, 1, 2, 3]

Big(O) Time Complexity Analysis

The optimal solution uses binary search, which has a time complexity of O(log n), where n is the length of the array. The final step of extracting the k elements has a time complexity of O(k). However, since k is always less than or equal to n, the overall time complexity is dominated by the binary search, making it O(log n).

Big(O) Space Complexity Analysis

The optimal solution has a space complexity of O(1) because it only uses a constant amount of extra space for variables like left, right, and mid. The returned list of k elements is part of the problem requirement, not additional space used by the algorithm.

Edge Cases

1. Empty Array: If the input array is empty, we should return an empty list.
2. k = 0: If k is 0, we should return an empty list.
3. k = n: If k is equal to the length of the array, we should return the entire array.
4. x is smaller than all elements: The binary search will ensure the leftmost elements are selected.
5. x is larger than all elements: The binary search will ensure the rightmost elements are selected.
6. Duplicate elements: The comparison x - arr[mid] > arr[mid + k] - x correctly handles duplicate elements in the array.

def find_k_closest_edge_cases(arr, k, x):
    if not arr or k == 0:
        return []
    if k == len(arr):
        return arr
    
    left = 0
    right = len(arr) - k

    while left < right:
        mid = (left + right) // 2
        if x - arr[mid] > arr[mid + k] - x:
            left = mid + 1
        else:
            right = mid

    return arr[left:left + k]