658. Find K Closest Elements 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

Example 1:
Input: 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]

Approach

Input: A sorted array arr, two integers k and x

Output: Find the k closest numbers to x, and return them sorted

This is a classic opposite-direction two pointers problem.

Imagine on a coordinate axis, the further away from a certain value, the larger the absolute difference. So this problem can be seen as finding the k numbers closest to x on the coordinate axis, or a window of length k, these numbers must appear in the arr array.

We can define two pointers left = 0 and right = len(arr) - 1.

• When right - left >= k, it means we still need to shrink the window.
• At this point, judge which side is closer to x.
• If abs(arr[left] - x) > abs(arr[right] - x), then we should discard the left number because the right number is closer to x.
• Otherwise, discard the right one.

Finally, we will get a window of size k [l, r]. Returning arr[l: r + 1] is the answer we want.

Implementation

python

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)
        left, right = 0, n - 1  # Initialize two pointers, pointing to the ends of the array

        # Ensure the final window size is k
        while right - left >= k:
            # Compare which end is further from x, discard the further side
            if abs(arr[left] - x) > abs(arr[right] - x):
                left += 1  # The left is further, move the left pointer right
            else:
                right -= 1  # The right is further or equally far, move the right pointer left

        # Return the k elements in the final window
        return arr[left:right + 1]

javascript

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
const findClosestElements = function(arr, k, x) {
    let left = 0;
    let right = arr.length - 1;

    while (right - left >= k) {
        if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
            left++;
        } else {
            right--;
        }
    }

    return arr.slice(left, right + 1);
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

658. Find K Closest Elements (English)658. 找到 K 个最接近的元素 (Chinese)