Skip to main content

658. Find K Closest Elements

medium

Return the k integers in a sorted array closest to a given value x. The slick O(log n + k) approach binary-searches for the window's left edge — most candidates default to a heap and lose the upper signal.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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. An integer a is closer to x than an integer b if |a - x| < |b - x|, or |a - x| == |b - x| and a < b.

Constraints

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

Examples

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]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The answer is a contiguous window of length k. You only need to find its left edge.

Hint 2

Binary-search candidate left edges l in [0, n - k]. Compare arr[l] and arr[l + k] against x to decide which side of l the better window lies on.

Hint 3

If x - arr[mid] > arr[mid + k] - x, the right window is strictly closer, so lo = mid + 1. Otherwise hi = mid.

Solution approach

Reveal approach

Binary search for the optimal left edge l of the answer window. Set lo = 0 and hi = n - k (l can be at most n - k since the window has length k). While lo < hi, compute mid = lo + (hi - lo) / 2. Compare the left candidate arr[mid] and the right candidate arr[mid + k] against x: if x - arr[mid] > arr[mid + k] - x, the window starting at mid + 1 contains a strictly closer element on its right side than mid's left side, so lo = mid + 1. Otherwise hi = mid. When lo == hi, return arr[lo..lo + k - 1]. The tiebreak rule (smaller value wins on equal distance) is automatic because we move the window leftward whenever distances tie. O(log(n - k) + k) total — log for the search, k for the slice. Beats the standard heap or two-pointer O(n) solutions.

Complexity

Time
O(log(n - k) + k)
Space
O(1)

Related patterns

  • binary-search
  • two-pointers
  • modified-binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • LinkedIn
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Find K Closest Elements and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →