Find K Closest Elements

Find K Closest Elements is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the Find First/Last Occurrence subpattern.

Problem statement

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

Example 1:

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

Output: [1,2,3,4]

Example 2:

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

Output: [1,1,2,3]

Constraints:

- 1 <= k <= arr.length

- 1 <= arr.length <= 104

- arr is sorted in ascending order.

- -104 <= arr[i], x <= 104

Topics and companies

Topics: Array, Two Pointers, Binary Search, Sliding Window, Sorting, Heap (Priority Queue).

Reported in interviews at Facebook, Microsoft, Google, Paypal.

How to practise Find K Closest Elements on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn + k) time and O(1) space.

Open Find K Closest Elements in the code editor, or read the Find K Closest Elements editorial for a worked solution with its approach and complexity analysis.

Where Find K Closest Elements sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• Find First/Last Occurrence subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Find K Closest Elements

Other problems that use the same Find First/Last Occurrence and Binary Search Patterns techniques:

• Find First and Last Position of Element in Sorted Array — Medium, same subpattern
• Binary Search — Easy, same pattern
• Capacity To Ship Packages Within D Days — Medium, same pattern
• Find in Mountain Array — Hard, same pattern
• Find K-th Smallest Pair Distance — Hard, same pattern
• Find Minimum in Rotated Sorted Array — Medium, same pattern