MediumArrayTwo PointersBinary SearchSliding WindowSortingHeapUpdated Sep 2026

658. Find K Closest Elements

Asked at Atlassian

Difficulty

Medium

Time

O(log(n - k) + k)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given a sorted integer array arr, plus two integers k and x. Return the k values from arr that are closest to x, and return them in ascending order.

"Closest" is measured by absolute distance |a - x|. If two values are equally far from x, the smaller one wins. For example, with x = 3, both 2 and 4 are distance 1 away, so 2 is preferred.

Because arr is already sorted, the k chosen values always form one contiguous block (a window) inside arr. Your job is to find where that block starts. The answer must be sorted, but since the block comes from a sorted array, you can just return it as-is.

Pick the k values nearest to x

arrk = 4 chosen1234501234The chosen values form one contiguous window becausearr is sorted.distance |a - 3|2101201234Value 5 has the largest distance, so it is the onedropped.
With x = 3, the four closest values are 1, 2, 3 and 4 — they sit together as one block.

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
Inputarr = [1,2,3,4,5], k = 4, x = 3
Output[1,2,3,4]
WhyDistances from 3 are: 1→2, 2→1, 3→0, 4→1, 5→2. The four smallest distances belong to 1, 2, 3 and 4. Note that 4 and 2 tie at distance 1, and 5 is farther than 1, so 5 is left out.
Example 2
Inputarr = [1,1,2,3,4,5], k = 4, x = -1
Output[1,1,2,3]
Whyx = -1 is far to the left, so the closest values are the smallest ones. Distances: 1→2, 1→2, 2→3, 3→4, 4→5, 5→6. Taking the four smallest gives the two 1s, then 2, then 3.

Asked At

1 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Brute force: compute distances for all elements, sort by distance, take first k

2

Use a max-heap of size k to keep track of closest elements

3

Binary search for the left boundary of the k-length window in the sorted array

4

Two pointers: start from x-index and expand outward comparing distances

5

Optimal: binary search for starting position, then return arr[start:start+k]

Optimal Approach

Use binary search to find the starting index of the k closest elements window. The answer must lie in the range [0, n-k]. For a candidate start position, compare arr[start] and arr[start+k-1] with x. If x - arr[start] > arr[start+k-1] - x, the window is too far left, so move right. Otherwise, move left. After binary search finds the optimal start, return arr[start..start+k-1]. This runs in O(log(n-k) + k) time, which is optimal for this problem.

Binary search for the window start

arrmid = 01234501234arr[mid]arr[mid+k]Compare arr[0] = 1 and arr[4] = 5 with x = 3: 3 - 1 =2 is not greater than 5 - 3 = 2, so keep the lefthalf.arrstart = 01234501234left and right meet at 0, so the best window starts atindex 0.search start in [0, n - k]if x - arr[mid] > arr[mid+k] - x: go rightelse: go leftanswer = arr[start : start + k]
Compare the two ends of a candidate window; if the left end is farther from x, the window must move right.
ComplexityTime O(log(n - k) + k)Space O(1)The binary search over the n - k + 1 possible window starts costs O(log(n - k)); copying out the k answers costs O(k), and no extra memory is used beyond the output.

What Trips People Up in Real Interviews

1

Clarify that the output must be sorted in ascending order, not by distance

2

Handle edge cases: k equals array length, x smaller than all elements or larger

3

Binary search approach: find the leftmost position where a window of k fits

4

For two pointers, note that arr[i] < arr[j] means arr[i] is closer when distances tie

5

Discuss trade-offs: heap is O(n log k), binary search is O(log n + k)

Solution Code

O(log(n - k) + k) time
def findClosestElements(arr, k, x):
    left, right = 0, len(arr) - k
    while left < right:
        mid = (left + right) // 2
        if x - arr[mid] > arr[mid + k] - x:
            left = mid + 1
        else:
            right = mid
    return arr[left:left + k]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Find K Closest Elements 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. A integer a is closer to x than integer b if |a - x| < |b - x|, or |a - x| == |b - x| and a < b. This problem tests binary search and sliding window techniques.

How do you solve Find K Closest Elements?

The optimal approach runs in O(log(n - k) + k) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Find K Closest Elements?

Find K Closest Elements is asked at Atlassian. It is a medium difficulty problem.

What are common mistakes on Find K Closest Elements?
  • Clarify that the output must be sorted in ascending order, not by distance
  • Handle edge cases: k equals array length, x smaller than all elements or larger
  • Binary search approach: find the leftmost position where a window of k fits
  • For two pointers, note that arr[i] < arr[j] means arr[i] is closer when distances tie
  • Discuss trade-offs: heap is O(n log k), binary search is O(log n + k)