Find K Closest Elements

You are given a sorted integer array arr, and two integers k and x. You have to find the k closest integers to x in the array.

Here’s a simple step-by-step approach to finding the k closest elements:

Algorithm

Binary Search: Since the array is sorted, we can use a binary search to find the index where x would fit in the array.
Initialize Pointers: Initialize two pointers, left and right, where left points to the index found in step 1 and right points to the next index.
Find Closest Elements: Compare the elements pointed by left and right to decide which one is closer to x, and move the pointers accordingly. Repeat this step until you have found k closest elements.
Gather Result: Return the k elements pointed by left and right.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        # Find the index where x would fit in the array
        index = bisect_left(arr, x)

        # Initialize pointers
        left = index - 1
        right = index

        # Find k closest elements
        while k > 0:
            if left < 0:
                right += 1
            elif right >= len(arr):
                left -= 1
            elif abs(arr[left] - x) <= abs(arr[right] - x):
                left -= 1
            else:
                right += 1
            k -= 1

        return arr[left+1:right]

Explanation

The code first finds the index where x would fit in the array.
It then initializes two pointers to find the closest elements on both sides of x.
The loop continues until k closest elements are found, moving the pointers based on which element is closer to x.
Finally, it returns the result as the portion of the array between the two pointers.

Insights

Time Complexity: The binary search takes (O(\log n)), and finding the closest elements takes (O(k)), resulting in a total time complexity of (O(\log n + k)).
Space Complexity: (O(1)) as we are only using constant extra space.

This solution efficiently finds the k closest elements in a sorted array using binary search and a two-pointer technique, fulfilling the given constraints.

Define the Terms

Define the Interface Input: array (integers) already sorted, k (size of the output), x (integer) Output: array (integers) - must be sorted

Analyze the Input and Output

[1,2,3,4,5]

|a - x| < |b - x| (whichever has the smallest diff wins) |a - x| == |b - x| and a < b (Tie breaking condition)

The output must contain the numbers with the closest to x, in sorted order

Find the diff (numbers are sorted by diff in ascending diff value) diff = [3,2,4,1,5] Grab the first k elements from the diff array output = [3,2,4,1] sort this output [1,2,3,4]

Keep a hash with with key as the element and the diff as the value. It may not be possible if duplicates are allowed in the input.

1 - 3 = 2 (a = 1) 2 - 3 = 1 (b = 2) 3 - 3 = 0 4 - 3 = 1 5 - 3 = 2

1 and 5 have the same difference, since a < b, we pick 1.

What are the four numbers that is closest to 3. x = 3

output: [2,3,4,1] because k = 4

Identify the Invariants

Identify the constraints

Search the Problem Space

Classify the Problem

Analyze the Examples

Solve the Problem by Hand

Describe the Pattern

Distill the Observations to Create Insights

Brute Force Approach

Analyze Time and Space Complexity

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# @param {Integer[]} arr
# @param {Integer} k
# @param {Integer} x
# @return {Integer[]}
def find_closest_elements(a, k, x)
   a.sort! do |a, b|
      if a == b
          a - b
      else
         (a-x).abs - (b-x).abs 
      end
   end
   a = a[0...k]
   
   a.sort!
end