658. Find K Closest Elements #

Problem #

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

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

Example 2:

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

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10^4
3. Absolute value of elements in the array and x will not exceed 10^4

UPDATE (2017/9/19): The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.

Problem Summary #

Given a sorted array and two integers k and x, find the k numbers in the array that are closest to x (with the smallest difference between the two numbers). The returned result must be sorted in ascending order. If two numbers have the same difference from x, choose the smaller number first.

Explanation:

1. The value of k is positive and is always smaller than the length of the given sorted array.
2. The array is not empty, and its length does not exceed 104
3. The absolute value of each element in the array and x does not exceed 104  

Update (2017/9/19): The parameter arr has been changed to an integer array (instead of a list of integers). Please reload the code definition to get the latest changes.

Solution Approach #

• Given an array, find an interval of length k in the array such that the distance between each element in this interval and x is the smallest in the entire array.
• This problem can be solved with two pointers, but the optimal solution is binary search. Since the interval length is fixed at K, the left boundary can be at most len(arr) - K (because after taking length K, the right boundary will exactly reach the rightmost end of the array). Perform binary search in the interval [0,len(arr) - K]. If the distance between a[mid] and x is greater than the distance between a[mid + k] and x, it means the target interval must be on the right, so continue binary search until finally exiting when low = high. The resulting low value is the left boundary of the final answer interval.

Code #

package leetcode

import "sort"

// Solution 1: binary search using library function
func findClosestElements(arr []int, k int, x int) []int {
	return arr[sort.Search(len(arr)-k, func(i int) bool { return x-arr[i] <= arr[i+k]-x }):][:k]
}

// Solution 2: hand-written binary search
func findClosestElements1(arr []int, k int, x int) []int {
	low, high := 0, len(arr)-k
	for low < high {
		mid := low + (high-low)>>1
		if x-arr[mid] > arr[mid+k]-x {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return arr[low : low+k]
}