{x}
blog image

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:

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]

 

Constraints:

  • 1 <= k <= arr.length
  • 1 <= arr.length <= 104
  • arr is sorted in ascending order.
  • -104 <= arr[i], x <= 104

658. Find K Closest Elements

This problem asks to find the k closest elements to x in a sorted array arr. The solution needs to be efficient and return the elements in ascending order.

Approach 1: Sorting

This approach directly uses the sorting capabilities of the language. We sort the array based on the absolute difference between each element and x. Then, we take the first k elements (the closest ones) and sort them again to ensure ascending order. This approach is simple but not the most efficient.

Time Complexity: O(N log N), where N is the length of the array, dominated by the initial sorting. Space Complexity: O(N) in the worst case, due to the creation of a new sorted array in Python and Java. In C++ and Go, it may be O(1) or O(N) depending on the implementation of the sort algorithm.

Approach 2: Binary Search and Two Pointers (Optimal)

This is a more efficient approach leveraging the sorted nature of the input array. The core idea is as follows:

  1. Find the starting point: Use binary search to find the index i of the element in arr that is closest to x. This gives us a good starting point for our search.

  2. Sliding Window: Maintain a window of size k centered around the closest element (i). Expand the window to the left and right until you find the optimal k elements. The two-pointer technique is used here for efficiently adjusting the window.

Time Complexity: O(log N + k), where N is the length of the array and k is the number of closest elements we want. Binary search takes O(log N), and the sliding window adjustment takes O(k) in the worst case (if k is relatively close to N, then the complexity would be O(N)). Space Complexity: O(k) in the worst case for storing the resulting array.

Approach 3: Binary Search (Improved)

This is a slightly optimized version of the binary search approach. Instead of finding the closest element explicitly, this approach directly searches for the left boundary of the window containing the k closest elements.

Time Complexity: O(log(N-k) + k). The binary search takes O(log(N-k)) to find the left boundary of the window, and then constructing the result takes O(k). Space Complexity: O(k) for storing the result.

Code Examples (Approach 2 and 3 are shown. Approach 1 is already in the original problem description):

The code examples provided in the original response illustrate the different approaches and use different programming languages. Approach 2 (Binary Search and Two Pointers) and Approach 3 (Optimized Binary Search) generally offer the best performance for this problem. The specific best choice would depend on the language implementation and compiler optimizations. Note that the Python and Go solutions for Approach 2 and Approach 3 are functionally identical in terms of time and space complexity.

Remember to consider the constraints given in the problem description when choosing an approach and implementing your solution. For large arrays and large values of k, the binary search-based approaches are significantly faster than the initial sorting approach.