Pattern this teaches:Heap and Top K
K Closest Points to Origin
A medium Heap interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Heap
- Sheets
- 2
- Core for
- 10 roles
The problem
You have points on a flat plane and a number k. Return the k points nearest to (0, 0), measuring by straight-line distance. Any order of those k points is accepted, and the test data never leaves a tie at the cut-off.
Example 1
- Input
- points = [[2,4],[1,1]], k = 1
- Output
- [[1,1]]
- Why
- Squared distances are 20 and 2: [1,1] is closer.
Example 2
- Input
- points = [[4,2],[6,-1],[-3,3]], k = 2
- Output
- [[-3,3],[4,2]]
- Why
- Squared distances: 18 for [-3,3], 20 for [4,2], 37 for [6,-1]. Keep the closest two.
Constraints
- 1 <= k <= points.length <= 10^4
- -10^4 <= points[i][0], points[i][1] <= 10^4
How to think about it
Updated 2026-09-29Comparing Euclidean distances never requires taking square roots: x^2 + y^2 preserves the exact relative ordering while avoiding floating-point inaccuracy. Because you only need the k closest, maintaining a boundary of the worst among your best allows filtering out distant points immediately.
Approaches, worst first
Full sort by distance
time O(n log n) · space O(n)
Compute squared distances for every coordinate, sort the entire array ascending, and slice the first k entries. Works in one pass of sorting, but pays to sequence all n points when only k are needed.
Bounded max-heap of size k
time O(n log k) · space O(k)
Keep a max-heap of size k keyed by squared distance. For each point, compare against the root: if closer, pop the furthest keeper and insert the newcomer. The heap retains only the k closest seen so far.
Quickselect partitioningWrite this one
time O(n) · space O(1)
Partition points around a pivot distance recursively until the pivot index lands precisely at k. Gives an unordered prefix containing the exact k closest elements without sorting them internally.
Where people lose marks · 3
- Calling Math.sqrt on every coordinate pair. Squaring avoids floating-point roundoff errors and eliminates an expensive mathematical function without altering relative ordering.
- Using a min-heap to collect the k closest instead of a max-heap. A min-heap capped at k would evict the closest points instead of the furthest ones.
- Forgetting that coordinates can be negative. Always square x and y or preserve signs during multiplication so distances never turn negative or miscalculated.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
More Heap problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .