Sliding Window - 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

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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

Constraints:

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

Solution 1 - Using sliding window technique, and binary search, lookup for window size of 'k' with closest elements to 'x'

The intution behind this solution is, since we want to find k nearest elements to x, we need to find where x is located first, but as per examples given above, x may or may not present in the input array. So, when we try to look for element x in the sorted array, and move either left or right side of array, we will try to find left and right boundaries such that they are the nearest values to x.

In this approach, we are going to apply sliding window technique using two pointers left and right, and since the array is sorted we will apply binary search to find element x or element near to x.

Implementation steps:

First, create two variables left, right that we will use to adjust the window, initialize left =0 and right = arr.length - k, the reason we initialize right with arr.length -k is because, we are trying to find element x using binary search, at the same time find the window of size k closest elements, and if we move left pointer towards right all the way to the right pointer, then we will not have k elements left. So, since we need k elements from that position, we are leaving k elements on the right side.
Next, run a while loop until left and right pointer cross each other, and check the following:
- Since the array is sorted, we will be doing a binary search to find element x, or a closer to that element, at the same time window window of size k which is closer to x, so compute mid = left + right / 2
- Check how far is the left pointer element to x than right pointer element, if x-arr[mid] > arr[mid+k] -x, then move left pointer to mid+1
- Otherwise, move right pointer to mid (inclusive of mid, in case of a tie, we want to consider smaller element)
Finally, return the window between left and left+k

import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.stream.Collectors; import java.util.stream.IntStream; public class FindKClosestElements { static List<Integer> findClosestElements(int[] arr, int k, int x) { int n = arr.length; int left = 0; // we are going to run sliding window with size as K. // so if left pointer reaches to right side of the array // we need atleast k elements to be there int right = n- k; // since the array is sorted, to find the window, we can use binary search while(left < right) { int mid = left + (right - left)/2; // we are trying to find element X/ element nearest to X in a sorted array // and the subarray of length k which has elements near to X // say if the input array is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], and k=4 x=3 // since right side values are greater than left side values // check whether left side is closer to x or right side value is closer to x // if they are same distance, then we have to take smaller value (i.e. left side value), so move towards left if(x-arr[mid] > arr[mid+k]-x) { left = mid+1; } else { right = mid; // suppose mid is the X, we need to consider mid } } return IntStream.of(Arrays.copyOfRange(arr, left, left+k)).boxed().collect(Collectors.toList()); } public static void main(String[] args) { System.out.println(findClosestElements(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, 4, 3)); System.out.println(findClosestElements(new int[]{1,2,3,4,5}, 4, 3)); System.out.println(findClosestElements(new int[]{1,2,3,4,5}, 4, -1)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input array arr.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: