Post

Binary Search - Find K Closest Elements

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty : Medium

Binary Search , Sliding Window

Problem

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. If distance of two integers are same from x, then choose the smaller one. x may not be present in the array arr.

Example 1:

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

Example 2:

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

Solution

  • The problem can be solved in O(log n+k) by first scanning the array to find the first closest element and then using two pointers to find k closent elements. The complexity arises when the target number x is not in arr.
  • :fire: One solution is to convert this to a Sliding Window & Binary Search problem. Since the array is already sorted, we can try to find the window in which the k elements exists (They will always be in a window).
  • We can start from right [or left] most and use the right [or left] pointer to keep track of the start of the window.

  • Lets use this example is the diagram:
    • Input : arr = [1,2,3,4,5,6,7], k = 4, x = 5
    • Output : [3,4,5,6]

image-20240403172854483

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def find_closest_elements(arr, k, x):
    # Start right ptr from len(arr)-k
    l, r = 0, len(arr)-k

    # l < r and not l <=r 
    # We do not want to run this
    # when l == r as this was already validated 
    while l < r:
        # Find the middle ptr
        mid = (l+r)//2

        if x-arr[mid] > arr[mid+k]-x:
            # if the current middle value is
            # farther away than the value after
            # the window then move the window
            # right -> The intention is to keep 
            # finding closest values
            l = mid+1
        else:
            # if the current middle value is
            # closer or equal than the value after
            # the window then move the window
            # left to the mid ptr
            r = mid  # Not m+1
    return arr[r:r+k]


print(find_closest_elements([1, 2, 3, 4, 5, 6, 7], 4, 5))
1
[3, 4, 5, 6]

Runtime Complexity

The runtime will be O(log n) as we are simply running a binary search.

This post is licensed under CC BY 4.0 by the author.