Find K Closest Elements

Interview Problem Interview Medium Array Binary Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.findClosestElements(arr, k, x). arr is ascending. Return the k closest values to x in ascending order; ties prefer the smaller value.

Starter code

class Solution:
    def findClosestElements(self, arr, k, x):
        pass

Test cases

centered

{
  "args": [
    [
      1,
      2,
      3,
      4,
      5
    ],
    4,
    3
  ]
}

Expected: [1,2,3,4]

Wizard outline

Step 1: Initialize Solution.findClosestElements
Replace the empty starter with the first real state owned by Solution.findClosestElements. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Left Of Array case
Complete the readable core algorithm for one representative Interview case. Compare the two values that compete when choosing between adjacent length-k windows.
Step 4: Harden the Tie Prefers Left boundary
Repair the reviewed boundary and pass the complete submission contract. Adjacent candidate windows differ only by arr[middle] versus arr[middle+k]. If the right competitor is closer, every optimum starts after middle; otherwise middle or a left start remains optimal, including ties that prefer smaller values.

Footguns and prerequisites

The binary-search range is over possible window starts 0 through len(arr)-k, not over individual answer elements.
arrays strings two pointers sliding window

Reviewed references

LeetCode 658 — Find K Closest Elements

Practice prerequisites

Discard Pairs with Two Pointers(opens in a new tab)
Discard Pairs with Two Pointers isolates every pair outside [left, right] has already been counted or proven too large, and no unresolved pair is skipped. That focused state discipline is required when implementing find k closest elements as a complete Interview Problem.

Recommended approach and implementation

Binary-search possible start indices. At middle, compare x-arr[middle] with arr[middle+k]-x to decide whether the better window starts to the right.

Why it works: Adjacent candidate windows differ only by arr[middle] versus arr[middle+k]. If the right competitor is closer, every optimum starts after middle; otherwise middle or a left start remains optimal, including ties that prefer smaller values.

class Solution:
    def findClosestElements(self, arr, k, x):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        left, right = 0, len(arr) - k
        while left < right:
            middle = (left + right) // 2
            if x - arr[middle] > arr[middle + k] - x:
                left = middle + 1
            else:
                right = middle
        return arr[left:left + k]