What is the brute force approach and complexity for Find K Closest Elements?

Sort a copy by (distance, value), keep k, then sort those k values with time complexity O(N log N) and space complexity O(N).

What is the optimal approach and complexity for Find K Closest Elements?

The answer is one block of k neighbours, so binary search where that block starts with optimal time complexity O(log(N − K) + K) and space complexity O(1).

How do you identify the pattern for Find K Closest Elements?

Look for key signals in the prompt: "k closest values to x" indicates The answer is k values that sit close to x. We need a block of k neighbours, not any k values.; "arr is sorted" indicates Neighbours in the array are neighbours in value. So we can search for the start of the block with binary search.; "tie → the smaller value" indicates The test must treat a tie as keep the left window. That is the hi = mid branch..

Find K Closest Elements

Medium·LeetCode #658 Pro OnlySlight Variation

LeetCode

Problem Statement

You get a sorted array arr (smallest to largest), plus two numbers: k and x. Return the k values in arr that are closest to x.

A value is closer to x when |value − x| is smaller. If two values are equally close, the smaller value wins. Return the answer sorted from smallest to largest.

Input

arr, a sorted list of integers. k, how many values to return. x, the number to compare against.

Output

The k closest values, sorted in ascending order.

Example 1

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

Output: [1, 2, 3, 4]

The distances to 3 are 2, 1, 0, 1, 2. The first three picks are 3, 2 and 4. Then 1 and 5 tie at distance 2, so the smaller one, 1, wins.

Example 2

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

Output: [1, 1, 2, 3]

Every value is to the right of −1, so the closest values are the smallest ones. The answer is the first four.

Constraints

• 1 ≤ k ≤ arr.length
• 1 ≤ arr.length ≤ 10^4
• arr is sorted in ascending order
• −10^4 ≤ arr[i], x ≤ 10^4

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“k closest values to x”

→ The answer is k values that sit close to x. We need a block of k neighbours, not any k values.

“arr is sorted”

→ Neighbours in the array are neighbours in value. So we can search for the start of the block with binary search.

“tie → the smaller value”

→ The test must treat a tie as keep the left window. That is the hi = mid branch.

Approach Complexity Ladder

Brute Force — sort by distance, take k, sort againO(N log N)O(N)

Sort a copy by (distance, value), keep k, then sort those k values

Better — max-heap of size k on (distance, value)O(N log K)O(K)

Keep the k closest values in a max-heap; sort the k values at the end

Optimal — binary search for the window startO(log(N − K) + K)O(1)

The answer is one block of k neighbours, so binary search where that block starts

Brute Force Intuition

Sort a copy of arr with the rule from the question: sort by distance to x, then by value. Keep the first k values, and sort those k values again so they come out in ascending order.

Recognition rule for this sub-pattern:

Score each item by distance; keep the K smallest scores.

Remember this · Heap — Top K

Trigger

"K largest / smallest / most frequent / closest", kth element, streaming top-K.

Think

Do I really need everything sorted, or only the best K?

Key question

Min-heap or max-heap of size K — which one lets me kick out the worst candidate?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Heap — Top K translate into production architectures and low-level memory mechanics.

LLD Real-World Story

High-Frequency Trading (HFT) Order Book

Price-time priority matching engine powered by heap buckets and tree maps.

Explore Track

C++ Internals

STL Containers & Allocator Internals

std::priority_queue container adapter and underlying heapify memory buffers.

Explore Track

K Closest Points to Origin